perm filename V2E.IN[TEX,DEK] blob sn#359280 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	folio 196 galley 1
C00016 00003	folio 198 galley 2
C00030 00004	folio 201 galley 3
C00044 00005	folio 204 galley 4
C00061 00006	folio 206 galley 5
C00078 00007	folio 209 galley 6
C00094 00008	folio 212 galley 7
C00103 00009	folio 214 galley 8
C00118 00010	folio 216 galley 9
C00136 00011	folio 220 galley 10
C00149 ENDMK
C⊗;
folio 196 galley 1
    0  {U0}{H10L12M29}|πW58320#Computer Programming!(Knuth/Addison-
    1  Wesley)!f.|4196!ch.|43!g.|41d|'{A6}!|9|7First 
    3  it is convenient to generalize De_nition A, since 
   11  the limit appearing there does not exist for 
   19  all sequences. Let us de_ne|'{A4}|v4Pr|){H12}({H10}|εS(n){H1
   24  2}){H10}|4α=↓|4|uw|πlim|4sup|uc|)|.|εn|1|¬M|1|¬X|)|4{H12}({H
   24  10}|≤n(n)/n{H12}){H10}!!|πPr{H12}({H10}|εS(n){H12}){H10}|4α=
   24  ↓|4|uw|πlim|4inf|uc|)|.|εn|1|¬M|1|¬X|)|4{H12}({H10}|≤n(n)/n{
   24  H12}){H10}.|J!(7)};{A9}|πThen Pr{H12}(|εS(n){H12}){H10}, 
   27  |πif it exists, is the common value of Pr{H12}({H10}|εS(n){H
   35  12}) |πand |v4Pr|){H12}({H10}|εS(n){H12}){H10}.|'
   38  !|9|7|πWe have seen that a |εk-|πdistributed 
   44  [0,|41) sequence leads to a |εk-|πdistributed 
   50  |εb|π-ary sequence, if |εU |πis replaced by |"l|εbU|"L. 
   58  |πOur _rst theorem shows that a converse result 
   66  is true:|'{A12}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡A|≡.|9|4|εLet 
   70  |↔b|"lb|βjU|βn|↔L|↔v|4α=↓|4U|β0,|4U|β1,|4U|β2,|4.|4.|4.|4be 
   71  a [0,|41) sequence. If the sequence|'{A9}|↔b|"lb|βjU|βn|"L|↔
   77  v|4α=↓|4|↔lb|βjU|β0|"L, |"lb|βjU|β1|"L, |"lb|βjU|β2|"L,|4.|4
   79  .|4.|;{A9}is a k-distributed b|βj-ary sequence 
   85  for all b|βj in an in⊂nite sequence of integers, 
   94  1|4|¬W|4b|β1|4|¬W|4b|β2|4|¬W|4b|β3|4|¬W|4αo↓|4αo↓|4αo↓|4, 
   95  then the original sequence |↔bU|βn|↔v is k-distributed.|'
  102  {A12}!|9|7|πAs an example of this theorem, suppose 
  109  that |εb|βj|4α=↓|42|gj. |πThe sequence |"l|ε2|gjU|β0|"L, 
  114  |"l2|gjU|β1|"L,|4.|4.|4. |πis essentially the 
  118  sequence of the _rst |εj |πbits of the binary 
  127  representation of |εU|β0,|4U|β1,|4.|4.|4.|4. 
  130  |πIf all these integer sequences are |εk-|πdistributed, 
  137  in the sense of De_nition |εD, |πthe real-valued 
  145  sequence |εU|β0,|4U|β1,|4.|4.|4. |πmust also 
  149  be |εk-|πdistributed in the sense of De_nition 
  156  B.|'{A12}|εProof of Theorem A.|9|4|πIf the sequence 
  163  |ε|"lbU|β0|"L, |"lbU|β1|"L,|4.|4.|4. |πis |εk-|πdistributed,
  166   it follows by the addition of probabilities 
  174  that Eq. (5) holds whenever each |εu|βj |πand 
  182  |εv|βj |πis a rational number with denominator 
  189  |εb. |πNow let |εu|βj,|4v|βj |πbe any real numbers, 
  197  and let |εu|ur|↔0|)j|)|4|¬E|4U|βJ|4|¬W|4U|ur|↔0|)j|)|4α+↓|41
  199  /b, v|ur|↔0|)j|)|4|¬E|4v|βj|4|¬W|4v|ur|↔0|)j|)|4α+↓|41/b.|;
  201  {A9}|πLet |εS(n) |πbe the statement that |εu|β1|4|¬E|4U|βn|4
  207  |¬W|4v|β1,|4.|4.|4.|4,|4u|βk|4|¬E|4U|βn|βα+↓|βk|βα_↓|β1|4|¬W
  207  |4v|βk. |πWe have|'{A9}Pr{H12}(|εS(n){H12}){H10}|4|¬E|4|πPr|
  210  ↔a|εu|ur|↔0|)1|)|4|¬E|4U|βn|4|¬W|4v|ur|↔0|)1|)|4α+↓|4|(1|d2b
  210  |)|4,|4.|4.|4.|4,|4u|ur|↔0|)k|)|4|¬E|4U|βn|βα+↓|βk|βα_↓|β1|4
  210  |¬W|4v|ur|↔0|)k|)|4α+↓|4|(1|d2b|)|↔s|'{A4}α=↓|4|↔av|ur|↔0|)1
  211  |)|4α_↓|4u|ur|↔0|)1|)|4α+↓|4|(1|d2b|)|↔s|4.|4.|4.|4|↔av|ur|↔
  211  0|)k|)|4α_↓|4u|ur|↔0|)k|)|4α+↓|4|(1|d2b|)|↔s;|?
  212  {A6}|πPr{H12}({H10}|εS(n){H12}){H10}|4|¬R|4|πPr|↔a|εu|ur|↔0|
  212  )1|)|4α+↓|4|(1|d2b|)|4|¬E|4U|βn|4|¬W|4v|ur|↔0|)1|),|4.|4.|4.
  212  |4,|4U|ur|↔0|)k|)|4α+↓|4|(1|d2b|)|4|¬E|4U|βn|βα+↓|βk|βα_↓|β1
  212  |4|¬W|4v|ur|↔0|)k|)|↔s|'{A4}α=↓|4|↔av|ur|↔0|)1|)|4α_↓|4u|ur|
  213  ↔0|)1|)|4α_↓|4|(1|d2b|)|↔s|4.|4.|4.|4|↔av|ur|↔0|)k|)|4α_↓|4u
  213  |ur|↔0|)k|)|4α_↓|4|(1|d2b|)|↔s.|1|?{A9}|πNow 
  215  |¬G(|εv|ur|↔0|)j|)|4α_↓|4u|ur|↔0|)j|)|4|¬N|41/b)|4α_↓|4(v|βj
  215  |4α_↓|4u|βj)|¬G|4|¬E|42/b; |πsince our inequalities 
  219  hold for all |εb|4α=↓|4b|βj, |πand since |εb|βj|4|¬M|4|¬X 
  226  |πas |εj|4|¬M|4|¬X, |πwe have|'{A9}(|εv|β1|4α_↓|4u|β1)|4.|4.
  230  |4.|4(v|βk|4α_↓|4u|βk)|4|¬E|4|πPr{H12}({H10}|εS(n){H12}){H10
  230  }|4|¬E|4|πPr{H12}({H10}|εS(n){H12})|4|¬E|4(v|β1|4α_↓|4u|β1)|
  230  4.|4.|4.|4(v|βk|4α_↓|4u|βk).|'{A9}!|9|7|πThe 
  232  next theorem is our main tool for proving things 
  241  about |εk-|πdistributed sequences.|'{A12}|≡T|≡h|≡e|≡o|≡r|≡e|
  244  ≡m |≡B|≡.|9|4|εLet |↔bU|βn|↔v be a k-distributed 
  250  [0,|41) sequence, and let f(x|β1,|4x|β2,|4.|4.|4.|4,|4x|βk) 
  255  be a Riemann-integrable function of k variables|*/;|\ 
  262  then|'{A9}|uw|πlim|uc|)|ε|.n|¬M|¬X|)|4|(1|d2n|)|4|¬K|uc|)0|¬
  263  Ej|¬Wn|)|4f(U|βj,|4U|βj|βα+↓|β1,|4.|4.|4.|4,|4U|βj|βα+↓|βk|β
  263  α_↓|β1)|'{A4}α=↓|4|↔j|ur1|)0|)|4.|4.|4.|4|↔j|ur1|)0|)|4f(x|β
  264  1,|4x|β2,|4.|4.|4.|4,|4x|βk)|4dx|β1|4.|4.|4.|4dx|βk.!(8)|?
  265  {A9}Proof.|9|4|πThe de_nition of a |εk-|πdistributed 
  270  sequence states that this result is true in the 
  279  special case that|'{A9}|εf(x|β1,|4.|4.|4.|4,|4x|βk)|4α=↓|4|↔
  282  A|(1,!!|d50,!!|)|(|πif!!|εu|β1|4|¬E|4x|β1|4|¬W|4v|β1,|4.|4.|
  282  4.|4,|4u|βk|4|¬E|4x|βk|4|¬W|4v|βk;|d5!|)|J!(9)|;
  283  {A9}|πTherefore Eq. (8) is true whenever |εf|4α=↓|4a|β1f|β1|
  289  4α+↓|4a|β2f|β2|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4a|βmf|βm 
  290  |πand when each |εf|βj |πis a function of type 
  299  (9); in otherwords, Eq. (8) holds whenever |εf 
  307  |πis a ``step-function;; obtained by (i) partitioning 
  314  the unit |εk-|πdimensional cube into subcells 
  320  whose faces are parallel to the coordinate axes, 
  328  and (ii) assigning a constant value to |εf |πon 
  337  each subcell.|'!|9|7Now let |εf |πbe any Riemann-integrable 
  345  function. If |ε|≤e |πis any positive number, 
  352  we know (by the de_nition of Riemann-integrability) 
  359  that there exist step functions |εf |πand |ε|=|¬∩f 
  367  |πsuch that |εf(x|β1,|4.|4.|4.|4,|4x|βk)|4|¬E|4f(x|β1,|4.|4.
  369  |4.|4,|4x|βk)|4|¬E|4|=|¬∩f(x|β1,|4.|4.|4.|4,|4x|βk), 
  370  |πand such that the di=erence of the integrals 
  378  of |εf |πand |ε|=|¬∩f |πis less than |ε|≤e. |πSince 
  387  Eq. (8) holds for |εf |πand |ε|=|¬∩f, |πand since|'
  396  {A9}|(|ε1|d2n|)|4|↔k|uc|)0|¬Ej|¬Wn|)|4f(U|βj,|4.|4.|4.|4,|4U
  396  |βj|βα+↓|βk|βα_↓|β1)|4|¬E|4|(1|d2n|)|4|↔k|uc|)0|¬Ej|¬Wn|)|4f
  396  (U|βj,|4.|4.|4.|4,|4U|βj|βα+↓|βk|βα_↓|β1)|5|;
  397  {A4}|hn|4|β0|β|¬E|βj|β|¬W|βn|4f(U|βj,|4.|4.|4.|4,|4U|βj|βα+↓
  397  |βk|βα_↓|β1)|4|n|¬E|4|(1|d2n|)|4|↔k|uc|)0|¬Ej|¬Wn|)|4|=|¬∩f(
  397  U|βj,|4.|4.|4.|4,|4U|βj|βα+↓|βk|βα_↓|β1),|;{A9}|πwe 
  399  conclude Eq. (8) is true also for |εf.|'{A12}!|9|7|πAs 
  408  the _rst application of this theorem, consider 
  415  the |εpermutation test |πdescribed in Section 
  421  3.3.2. Let (|εp|β1,|4p|β2,|4.|4.|4.|4,|4p|βk) 
  424  |πbe any permutation of the numbers 1,|42,|4.|4.|4.|4,|4|εk;
  430   |πwe want to show that|'{A9}Pr(|εU|βn|βα+↓|βp|m1|βα_↓|β1|4|
  436  ¬W|4U|βn|βα+↓|βp|m2|βα_↓|β1)|4α=↓|41/k*3.|J!(10)|;
  437  {A9}|πTo prove this, assume that the sequence 
  444  |↔b|εU|βn|↔v |πis |εk-|πdistributed, and let|'
  449  {A9}|εf(x|β1,|4.|4.|4.|4,|4x|βk)|4α=↓|4|(1,!!|d50,!!|)|(|πif
  449  !!|εx|βp|m1|4|¬E|4x|βp|m2|4|¬E|4αo↓|4αo↓|4αo↓|4|¬E|4x|βp|mk|
  449  d5!|)|;{A9}|πWe have|'{A3}Pr(|εU|βn|βα+↓|βp|m1|βα_↓|β1|4|¬W|
  452  4U|βn|βα+↓|βp|m2|βα_↓|β1|4|¬W|4αo↓|4αo↓|4αo↓|4|¬W|4U|βn|βα+↓
  452  |βp|mk|βα_↓|β1)|'{A4}|∂α=↓|4|↔j|ur1|)0|)|4.|4.|4.|4|↔j|ur1|)
  453  0|)|4f(x|β1,|4.|4.|4.|4,|4x|βk)|4dx|β1|4.|4.|4.|4dx|βk|h|m1|
  453  4α=↓|4k*3|4.|n|?{A4}|Lα=↓|4|↔j|ur1|)0|)|4dx|βp|mk|4|↔j|urx|βp
  454  |mk|)0|)|4.|4.|4.|4|↔j|urx|βp|m3|)0|)|4dx|βp|m2|4|↔j|urx|βp|
  454  m2|)0|)|4dx|βp|m1|4α=↓|4|(1|d2k*3|)|4.>{A9}|π|≡C|≡o|≡r|≡o|≡l|
  455  ≡l|≡a|≡r|≡y |≡P|≡.|9|4|εIf a [0,|41) sequence 
  460  is k-distributed, it satis⊂es the permutation 
  466  test of order k, in the sense of Eq. (10).|'{A12}!|9|7|πWe 
  477  can also show that the |εserial correlation test 
  485  |πis satis_ed:|'{A12}|≡C|≡o|≡r|≡o|≡l|≡l|≡a|≡r|≡y 
  488  |≡S|≡.|9|4|εIf a [0,|41) sequence is (k|4α+↓|41)-distributed
  493  , the serial correlation coe∀cient between U|βn 
  500  and U|βn|βα+↓|βk tends to zero|*/:|'|\{A9}|uw|πlim|uc|)|.|εn|
  505  ¬M|¬X|)|4|(|(1|d2n|)|4|¬K|4U|βjU|βj|βα+↓|βk|4α_↓|4|↔a|(1|d2n
  505  |)|4|¬K|4U|βj|↔s|↔a|(1|d2n|)|4|¬K|4U|βj|βα+↓|βk|↔s|d1|↔K|v2|
  505  ↔a|(1|d2n|)|4|¬K|4U|ur2|)j|)|4α_↓|4|↔a|(1|d2n|)|4|¬K|4U|βj|↔
  505  s|g2|↔s|↔a|(1|d2n|)|4|¬K|4U|ur2|)jα+↓k|)|4α_↓|4|↔a|(1|d2n|)|
  505  4|¬K|4U|βj|βα+↓|βk|↔s|g2{H12}|↔s{H10}|)|)|4α=↓|40.|;
  506  {A9}(|πAll summations here are for 0|4|¬E|4|εj|4|¬W|4n.)|'
  512  {A12}Proof.|9|4|πBy Theorem B, the quantities|'
  517  {A9}|(|ε1|d2n|)|4|¬K|4U|βjU|βj|βα+↓|βk,!!|(1|d2n|)|4|¬K|4U|u
  517  r2|)j|),!!|(1|d2n|)|4|¬K|4U|ur2|)jα+↓k|),!!|(1|d2n|)|4|¬K|4U
  517  |βj,!!|(1|d2n|)|4|¬K|4U|βj|βα+↓|βk|;{A9}|πtend 
  519  to the respective limits |f1|d34|), |f1|d33|), 
  525  |f1|d33|), |f1|d32|), |f1|d32|) as |εn|4|¬M|4|¬X.|'
  530  |Hu{U0}{H10L12M29}|πW58320#Computer Programming!(Knuth/Addis
folio 198 galley 2
  531  on-Wesley)!f.|4198!ch.|43!g.|42d|'{A6}!|9|7Let 
  533  us now consider some slightly more general distribution 
  541  properties of sequences. We have de_ned the |εk-|πdistributi
  548  on property for all adjacent |εk-|πtuples; for 
  555  example, a sequence is 2-distributed if and only 
  563  if the points|'{A6}{A3}(|εU|β0,|4U|β1),!!(U|β1,|4U|β2),!!(U|
  566  β2,|4U|β3),!!(U|β3,|4U|β4),!!(U|β4,|4U|β5),!!.|4.|4.|;
  567  {A9}|πare equidistributed in the unit square. 
  573  It is quite possible, however, that the alternate 
  581  pairs of points, (|εU|β1,|4U|β2), (U|β3,|4U|β4), 
  586  (U|β5,|4U|β6),|4.|4.|4. |πare not themselves 
  590  equi|-distributed; if the density of points (|εU|β2|βn|βα_↓|
  596  β1, U|β2|βn) |πis de_cient in some area, the 
  604  other points (|εU|β2|βn, U|β2|βn|βα+↓|β1) |πmight 
  609  compensate for it. For example, the periodic 
  616  binary sequence|'{A9}|ε|↔bX|βn|↔v|4α=↓|40, 0, 
  620  0, 1,!0, 0, 0, 1,!1, 1, 0, 1,!1, 1, 0, 1,!0, 
  631  0, 0, 1,!.|4.|4.|4,!(11)|?{A9}|πwith a period 
  637  of length 16, is seen to be 3-distributed; yet 
  646  the sequence of even-numbered elements |↔b|εX|β2|βn|↔v|4α=↓|
  651  40,|40,|40,|40,|41,|40,|41,|40,|4.|4.|4. |πhas 
  653  three times as many zeros as ones, while the 
  662  subsequence of odd-numbered elements |↔b|εX|β2|βn|βα+↓|β1|↔v
  666  |4α=↓|40,|41,|40,|41,|41,|41,|41,|41,|4.|4.|4. 
  667  |πhas three times as many ones as zeros.|'!|9|7If 
  676  a sequence |↔b|εU|βn|↔v |πis |¬X-distributed, 
  681  the example above shows that it is not at all 
  691  obvious that the subsequence of alternate terms 
  698  |↔b|εU|β2|βn|↔v|4α=↓|4U|β0, U|β2, U|β4, U|β6,|4.|4.|4. 
  702  |πis |¬X-distributed or even 1-distributed. But 
  708  we shall see that |ε|↔bU|β2|βn|↔v |πis, in fact, 
  716  |¬X-distributed, and much more is also true.|'
  723  {A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|≡n |≡E|≡.|9|4|εA 
  725  [0,|41) sequence |↔bU|βn|↔v is said to be (m,|4k)-distribute
  732  d if|'{A9}|πPr(|εu|β1|4|¬E|4U|βm|βn|βα+↓|βj|4|¬W|4v|β1, 
  735  u|β2|4|¬E|4U|βm|βn|βα+↓|βj|βα+↓|β1|4|¬W|4v|β2,|4.|4.|4.|4, 
  736  u|βk|4|¬E|4U|βm|βn|βα+↓|βj|βα+↓|βk|βα_↓|β1|4|¬W|4v|βk)|'
  737  {A4}α=↓|4(v|β1|4α_↓|4u|β1)|4.|4.|4.|4(v|βk|4α_↓|4u|βk)|?
  738  {A9}for all choices of real numbers u|βr, v|βr 
  746  with 0|4|¬E|4u|βr|4|¬W|4v|βr|4|¬E|41 for 1|4|¬E|4r|4|¬E|4k, 
  750  and for all integers j with 0|4|¬E|4j|4|¬W|4m.|'
  757  {A12}|πThus a |εk-|πdistributed sequence is the 
  763  special case |εm|4α=↓|41 |πin De_nition E; the 
  770  case |εm|4α=↓|42 |πmeans that the |εk-tuples 
  776  in even positions must have the same density 
  784  as the |εk-|πtuples in even positions must have 
  792  the same density as the |εk-|πtuples in odd positions, 
  801  etc.|'!|9|7Several properties of De_nition E 
  807  are obvious:|'{A9}!|9|7|εAn (m,|4k)-distributed 
  811  sequence is (m,|4k)-distributed for 1|4|¬E|4|≤k|4|¬E|4k.|J!(
  815  12)|'{A6}!|9|7An (m,|4k)-distributed sequence 
  819  is (d,|4k)-distributed for all divisors|J!(13)|'
  824  !!!|9|5d of m.|'{A9}|πWe can de_ne the concept 
  832  of an (|εm,|4k)-|πdistributed |εb-|πary sequence, 
  837  as in De_nition D; and the proof of Theorem A 
  847  remains valid for (|εm,|4k)-|πdistributed sequences.|'
  852  !|9|7The next theorem, which is in many ways 
  860  rather surprising, shows that the property of 
  867  being |¬X-distributed is very strong indeed, 
  873  much stronger than we imagined it to be when 
  882  we _rst considered the de_nition of the concept.|'
  890  {A12}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡C (Ivan Niven and 
  895  H. S. Zuckerman).|9|4|εAn |¬X-distributed sequence 
  900  is (m,|4k)-distributed for all positive integers 
  906  m and k.|'{A12}Proof.|9|4|πIt su∃ces to prove 
  913  the theorem for |εb-|πary sequences, by using 
  920  the generalization of Theorem A just mentioned. 
  927  Furthermore, we may assume that |εm|4α=↓|4k: 
  933  |πfor, by (12) and (13), the sequence will be 
  942  (|εm,|4k)-|πdistributed if it is (|εmk,|4mk)-|πdistributed.|
  946  '!|9|7So we will prove that |εany |¬X-distributed 
  954  b-ary sequence X|β0, X|β1,|4.|4.|4. is (m,|4m)-distributed 
  960  for all positive integers m. |πOur proof is a 
  969  simpli_cation of the proof given by Niven and 
  977  Zuckerman in |εPaci⊂c Journal of Mathematics 
  983  |≡1 (1951), 103<109.|'!|9|7|πThe theorem is proved 
  990  by making use of an important idea which is useful 
 1000  in so many mathematical arguments: ``If the sum 
 1008  of |εm |πquantities and the sum of their squares 
 1017  are both consistent with the hypothesis that 
 1024  the |εm |πquantities are equal, that hypothesis 
 1031  is true.'' In a strong form, this principle may 
 1040  be stated as follows:|'{A12}|≡L|≡e|≡m|≡m|≡a |≡E|≡.|9|4|εGive
 1045  n m sequences of numbers |↔by|βj|βn|↔v|4α=↓|4y|βj|β0,|4y|βj|
 1050  β1,|4y|βj|β2,|4.|4.|4. for 1|4|¬E|4j|4|¬E|4m, 
 1053  suppose that|'{A3}!|7|uw|πlim|uc|)|.|εn|¬M|¬X|)|4(y|β1|βn|4α
 1055  +↓|4y|β2|βn|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4y|βm|βn)|4|∂α=↓|4m|≤a,
 1055  |4|4|;{B6}(14)|?{B6}| |uw|πlim|4sup|uc|)|.|εn|¬M|¬X|)|4(y|ur
 1057  2|)1n|)|4α+↓|4y|ur2|)2n|)|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4y|ur2|)m
 1057  n|))|4|L|¬E|4m|≤a|g2.>{A9}Then for each j, |πlim|ε|βn|β|¬M|β
 1062  |¬X|4y|βj|βn exists and equals |≤a.|'{A12}!|9|7|πAn 
 1068  incredibly simple proof of this lemma is given 
 1076  in exercise 9.|'{A12}!|9|7Now to continue our 
 1083  proof of Theorem C. Let |εx|4α=↓|4x|β1x|β2|4.|4.|4.|4x|βm 
 1089  |πbe a |εb-|πary number, and say that |εx occurs 
 1098  |πat position |εp |πof the sequence if |εX|βp|βα_↓|βm|βα+↓|β
 1105  1X|βp|βα_↓|βm|βα+↓|β2|4.|4.|4.|4X|βp|4α=↓|4x. 
 1106  |πLet |ε|≤n|βj(n) |πbe the number of occurrences 
 1113  of |εx |πat |πposition |εp |πwhen |εp|4|¬W|4n 
 1120  |πand |εp|4|πmod|4|εm|4α=↓|4j. |πLet |εy|βj|βn|4α=↓|4|≤n|βj(
 1123  n)/n; |πwe wish to prove that|'{A3}|uwlim|uc|)|.|εn|¬M|¬X|)|
 1129  4y|βj|βn|4α=↓|41/mb|gm.|J!(15)|;{A9}!|9|7|πFirst 
 1131  we know that|'{A3}|uwlim|uc|)|.|εn|¬M|¬X|)|4(y|β0|βn|4α+↓|4y
 1134  |β1|βn|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4y|β(|βm|βα_↓|β1|β)|βn)|4α=↓
 1134  |41/b|gm,|J!(16)|;{A9}|πsince the sequence is 
 1139  |εm-|πdistributed. By Lemma E and Eq. (16), the 
 1147  theorem will be proved if we can show that|'{A3}|uwlim|4sup|
 1156  uc|)|.|εn|¬M|¬X|)|4(y|ur2|)0n|)|4α+↓|4y|ur2|)1n|)|4α+↓|4αo↓|
 1156  4αo↓|4αo↓|4α+↓|4y|ur2|)(mα_↓1)n|))|4|¬E|41/mb|g2|gm.|J!(17)|
 1156  ;{A9}!|9|7|πThis inequality is not obvious yet; 
 1163  some rather delicate maneuvering is necessary 
 1169  before we can prove it. Let |εq |πbe a multiple 
 1179  of |εm, |πand consider|'{A9}|εC(n)|4α=↓|4|↔k|uc|)0|¬Ej|¬Wm|)
 1183  |1|1|↔a|(|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓|4q)|d52|)|↔s.|J!(18)|
 1183  ;{A9}|πThis is the number of pairs of occurrences 
 1192  of |εx |πin positions |εp|β1,|4p|β2 |πwith |εn|4α_↓|4q|4|¬E|
 1198  4p|β1|4|¬W|4p|β2|4|¬W|4n |πand with |εp|β2|4α_↓|4p|β1 
 1202  |πa multiple of |εm. |πConsider now the sum|'
 1210  {A3}|εS|βN|4α=↓|4|↔k|uc|)1|¬En|¬ENα+↓q|)|4C(n).|J!(19)|;
 1211  {A9}|πEach pair of occurrences of |εx |πin positions 
 1219  |εp|β1,|4p|β2 |πwith |εp|β1|4|¬W|4p|β2|4|¬W|4p|β1|4α+↓|4q, 
 1222  p|β2|4α_↓|4p|β1 |πa multiple of |εm, |πand |εp|β1|4|¬E|4N, 
 1229  |πis counted |εp|β1|4α+↓|4q|4α_↓|4p|β2 |πtimes 
 1233  in the total |εS|βN (|πnamely, when |εp|β2|4|¬W|4n|4|¬E|4p|β
 1239  1|4α+↓|4q); |πand the pairs of such occurrences 
 1246  with |εN|4|¬W|4p|β1|4|¬W|4p|β2|4|¬W|4N|4α+↓|4q 
 1248  |πare counted |εN|4α+↓|4q|4α_↓|4p|β2 |πtimes.|'
 1252  !|9|7Let |εd|βt(n) |πbe the number of pairs of 
 1260  oc urrences of |εx |πin positions |εp|β1,|4p|β2 
 1267  |πwith |εp|β1|4α+↓|4t|4α=↓|4p|β2|4|¬W|4n. |πThe 
 1270  analysis above shows that|'{A3}|ε|↔k|uc|)0|¬Wt|¬Wq/m|)|4(q|4
 1274  α_↓|4mt)|4d|βm|βt(N|4α+↓|4q)|4|¬R|4S|βN|4|¬R|4|↔k|uc|)0|¬Wt|
 1274  ¬Wq/m|4(q|4α_↓|4mt)|4d|βm|βt(N).|J!(20)|;{A9}|πSince 
 1276  the original sequence is |εq-|πdistributed,|'
 1281  {A9}|uwlim|)|.|εN|¬M|¬X|)|4|(1|d2N|)|4d|βm|βt(N)|4α=↓|41/b|g
 1281  2|gm|J!(21)|;{A9}|πfor all |εo|4|¬W|4t|4|¬W|4q/m, 
 1285  |πand therefore by (20)|'{A9}|∂|uwlim|uc|)|ε|.N|¬M|¬X|)|4|(S
 1289  |βN|d2N|)|4α=↓|1|1|↔k|uc|)0|¬Wt|¬Wq/m|)|1|1(q|4α_↓|4mt)/b|g2
 1289  |gm|;{A4}|h|L|βN|β|¬M|β|¬X|4S|βN|4|nα=↓|4q(q|4α_↓|4m)/2mb|g2
 1290  |gm.|J!(22)>{A9}|πThis fact will prove the theorem, 
 1297  after some manipulation.|'|Hu*?*?{U0}{H10L12M29}|πW58320#Compu
folio 201 galley 3
 1300  ter Programming!(Knuth/Addison-Wesley)!f.|4201!ch.|43!g.|43d
 1301  |'{A6}!|9|7By De_nition,|'{A3}|ε2S|βN|4α=↓|4|↔k|uc|)1|¬En|¬E
 1304  Nα+↓q|)|4|↔k|uc|)0|¬Ej|¬Wm|)|4{H12}({H10}(|≤n|βj(n)|4α_↓|4|≤
 1304  n|βj(n|4α_↓|4q))|g2|4α_↓|4(|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓|4q)
 1304  ){H12}){H10},|;{A9}|πand we can remove the unsquared 
 1311  terms by applying (16) to get|'{A6}{A3}|uwlim|uc|)|.|εN|¬M|¬
 1317  X|)|4|(T|βN|d2N|)|4α=↓|4q(q|4α_↓|4m)/mb|g2|gm|4α+↓|4q/b|gm,|
 1317  J!(23)|;{A3}|πwhere|'|εT|βN|4α=↓|4|↔k|uc|)1|¬En|¬ENα+↓q|)|4|
 1319  ↔k|uc|)0|¬Ej|¬Wm|)|4{H12}({H10}|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓
 1319  |4q){H12}){H10}|g2.|;{A9}!|9|7|πUsing the inequality|'
 1323  {A6}|(|ε1|d2r|)|1|1|↔a|↔k|uc|)1|¬Ej|¬Er|)|1|1a|βj|↔s|g2|4|¬E
 1323  |4|↔k|uc|)1|¬Ej|¬Er|)|4a|ur2|)j|)|;{A9}(|πcf. 
 1325  exercise 1.2.3<30), we _nd that|'{A9}|uwlim|4sup|uc|)|.|εN|¬
 1330  M|¬X|)|4|↔k|uc|)0|¬Ej|¬Wm|)|4|(1|d2N(N|4α+↓|4q)|)|4|↔a|↔k|uc
 1330  |)1|¬En|¬ENα+↓q|)|1|1(|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓|4q){H12}
 1330  ){H10}|↔s|g2|'{A2}|¬E|4q(q|4α_↓|4m)/mb|g2|gm|4α+↓|4q/b|gm.!(
 1331  24)|?{A6}|πWe also have|'{A3}|εq|≤n|βj(N)|4|¬E|4|↔k|uc|)N|¬W
 1335  n|¬ENα+↓q|)|1|1|≤n|βj(n)|4α=↓|4|↔k|uc|)1|¬En|¬ENα+↓q|)|1|1{H
 1335  12}({H10}|≤n|βj(n)|4α_↓|4|≤n|βj(n|4α_↓|4q){H12}){H10}|4|¬E|4
 1335  q|≤n|βj(N|4α+↓|4q),|;{A9}|πand putting this into 
 1340  (24) gives|'{A3}|uwlim|4sup|uc|)|.|εN|¬M|¬X|)|4|↔k|uc|)0|¬Ej
 1342  |¬Wm|)|1|1{H12}({H10}|≤n|βj(N)/N{H12}){H10}|g2|4|¬E|4(q|4α_↓
 1342  |4m)/qmb|g2|gm|4α+↓|41/qb|gm.|J!(25)|;{A9}|πThis 
 1344  formula has been proved whenever |εq |πis a multiple 
 1353  of |εm, |πand if we let |εq|4|¬M|4|¬X |πwe obtain 
 1362  (17), completing the proof.|'!|9|7For a possibly 
 1369  simpler proof, see J. W. S. Cassels, |εPaci⊂c 
 1377  Journal of Mathematics |≡2 (1952), 555<557.|'
 1383  {A12}|π!|9|7Exercises 29 and 30 illustrate the 
 1389  nontriviality of this theorem, and they also 
 1396  illustrate the fact, indicated in (25), that 
 1403  a |εq-|πdistributed sequence will have probabilities 
 1409  deviating from the true (|εm,|4m)-|πdistribution 
 1414  probabilities by essentially 1/|¬H|v4|εq|) |πat 
 1419  most. The full hypothesis of |ε|¬X-|πdistribution 
 1425  is necessary for the proof of the theorem.|'!|9|7As 
 1434  a result of Theorem C, we can prove that an |ε|¬X-|πdistribu
 1444  ted sequence passes the serial test, the ``maximum 
 1452  of |εt'' |πtest, and the tests on subsequences 
 1460  mentioned in Section 3.3.2. It is not hard to 
 1469  show that the gap test, the poker test, and the 
 1479  run test are also satis_ed (see exercises 12 
 1487  through 14); the coupon collector's test is considerably 
 1495  more di∃cult to deal with, but it too is satis_ed 
 1505  (see exercises 15 and 16).|'{A12}!|9|7The existence 
 1512  of |¬X-distributed sequences of a rather simple 
 1519  type is guaranteed by the next theorem.|'{A12}|≡T|≡h|≡e|≡o|≡
 1526  r|≡e|≡m |≡F (J. Franklin).|9|4|εThe [0,|41) sequence 
 1532  U|β0,|4U|β1,|4.|4.|4.|4, with|'{A9}U|βn|4α=↓|4(|≤u|gn|4|πmod
 1534  |41)|J!(26)|;{A9}|εis |¬X-distributed for almost 
 1539  all real numbers |≤u|4|¬Q|41. That is, the set|'
 1547  {A9}|¬T|≤u|4|¬G|4|≤u|4|¬Q|41 |πand (26) is not 
 1552  |¬X-distributed|¬Y|;{A9}|εis of measure zero.|'
 1557  {A12}!|9|7|πThe proofs of this theorem and some 
 1564  generalizations are given in Franklin's paper 
 1570  quoted below.|'{A12}!|9|7Franklin has shown that 
 1576  |ε|≤u |πmust be a transcendental number for (26) 
 1584  to be |¬X-distributed. The powers (|ε|≤p|gn|4|πmod|41) 
 1590  have been laboriously computed for |εn|4|¬E|410000, 
 1596  |πusing multiple-precision arithmetic, and the 
 1601  most signi_cant 35 bits of each of these numbers, 
 1610  stored on a disk _le, have been sucessfully used 
 1619  as a source of uniform deviates. We have the 
 1628  interesting situation that, by Theorem F, the 
 1635  probability that the powers (|ε|≤p|gn|4|πmod|41) 
 1640  are |¬X-distributed is equal to 1; yet because 
 1648  there are uncountably many real numbers, this 
 1655  gives us no information as to whether the sequence 
 1664  is really |¬X-distributed or not. It is a fairly 
 1673  safe bet that nobody in our lifetimes will ever 
 1682  |εprove |πthat this particular sequence is |εnot 
 1689  |π|¬X-distributed; but it might not be. Because 
 1696  of these considerations, one may legitimately 
 1702  wonder if there is any |εexplicit |πsequence 
 1709  which is |¬X-distributed; i.e., |εis there an 
 1716  algorithm to compute real numbers U|βn for all 
 1724  n|4|¬R|40, such that the sequence |↔bU|βn|↔v 
 1730  is |¬X-distributed? |πThe answer is yes, as shown 
 1738  for example by the author in |εBIT |≡5 (|π1965), 
 1747  246<250. The sequence constructed there consists 
 1753  entirely of rational numbers; in fact, each number 
 1761  |εU|βn |πhas a terminating representation in 
 1767  the binary number system. Another construction 
 1773  of an explicit |¬X-distributed sequence, somewhat 
 1779  more complicated than the sequence just cited, 
 1786  follows from Theorem W below. See also N. M. 
 1795  Korobov, |εIzv. Akad. Nauk SSSR |π|≡2|≡0 (1956), 
 1802  649<660.|'{A12}|≡C|≡.|9|≡D|≡o|≡e|≡s |=|¬X|¬X|≡-|≡d|≡i|≡s|≡t|
 1804  ≡r|≡i|≡b|≡u|≡t|≡e|≡d|4|≡α=↓|4|≡r|≡a|≡n|≡d|≡o|≡m|≡?|9|4In 
 1805  view of all the above theory about |¬X-distributed 
 1813  sequences, we can be sure of one thing: the concept 
 1823  of an |¬X-distributed sequence is an important 
 1830  one in mathematics. There is also a good deal 
 1839  of evidence that the following statement is a 
 1847  valid formulation of the intuitive idea of randomness:|'
 1855  {A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|≡n |≡R|≡1|≡.|9|4|εA 
 1857  [0,|41) sequence is de⊂ned to be ``random'' if 
 1865  it is an |¬X-distributed sequence.|'{A12}|πWe 
 1871  have seen that sequences meeting this de_nition 
 1878  will satisfy all the statistical tests of Section 
 1886  3.3.2 and many more.|'!|9|7Let us attempt to 
 1894  criticize this de_nition objectively. First of 
 1900  all, is every ``truly random'' sequence |¬X-distributed? 
 1907  There are uncountably many sequences |εU|β0,|4U|β1,|4.|4.|4.
 1912   |πof real numbers between zero and one. If a 
 1922  truly random number generator is sampled to give 
 1930  values |εU|β0,|4U|β1,|4.|4.|4.|4, |πany of the 
 1935  possible sequences may be considered equally 
 1941  likely, and some of the sequences (indeed, uncountably 
 1949  many of them) are not even equi|-distributed. 
 1956  On the other hand, using any reasonable de_nition 
 1964  of probability on this space of all possible 
 1972  sequences leads us to conclude that a random 
 1980  sequence is |¬X-distributed |εwith probability 
 1985  one. |πWe are therefore led to formalize Franklin's 
 1993  de_nition of randomness (as given at the beginning 
 2001  of this section) in the following way:|'{A12}|≡D|≡e|≡_|≡n|≡i
 2008  |≡t|≡i|≡o|≡n |≡R|≡2|≡.|9|4|εA [0,|41) sequence 
 2012  |↔bU|βn|↔v is de⊂ned to be ``random'' if, whenever 
 2020  P is a property such that P(|↔bV|βn|↔v) holds 
 2028  with probability one for a sequence |↔bV|βn|↔v 
 2035  of independent samples of random variables from 
 2042  the uniform distribution, then P(|↔bU|βn|↔v) 
 2047  is true.|'!|9|7|πIs it perhaps possible that 
 2054  De_nition R1 is equivalent to De_nition R2? Let 
 2062  us try out some possible objections to De_nition 
 2070  R1, and see whether these cricicisms are valid.|'
 2078  !|9|7In the _rst place, De_nition R1 deals only 
 2086  with limiting properties of the sequence as |εn|4|¬M|4|¬X. 
 2094  |πThere are |¬X-distributed sequences in which 
 2100  the _rst million elements are all zero; should 
 2108  such a sequence be considered random?|'!|9|7This 
 2115  objection is not very valid. If |εe |πis any 
 2124  positive number, there is no reason why the _rst 
 2133  million elements of a sequence should not all 
 2141  be less than |ε|≤e; |πas pointed out earlier 
 2149  in this section, there is no legitimate way to 
 2158  say if a _nite sequence is random or not. With 
 2168  probability one, a truly random sequence contains 
 2175  in_nitely many runs of a million consecutive 
 2182  elements less than |ε|≤e, |πso why can't this 
 2190  happen at the beginning of the sequence?|'!|9|7On 
 2198  the othe{U0}{H10L12M29}|πW58320#Computer Programming!(Knuth/
folio 204 galley 4
 2200  Addison-Wesley)!f.|4204!ch.|43!g.|44d|'{A6}!|9|7Now 
 2202  let |εP |πbe the property that |εno |πelement 
 2210  of the sequence is equal to zero; again, |εP 
 2219  |πis true with probability one, so by De_nition 
 2227  R2 any sequence with a zero rlrment is not random. 
 2237  More generally, however, let |εX|β0 |πbe any 
 2244  _xed number between zero and one, and let |εP 
 2253  |πbe the property that no element of the sequence 
 2262  is equal to |εx|β0; |πDe_nition R2 now says that 
 2271  no random sequence may contain the element |εx|β0*3 
 2279  |πWe can now prove that |εno sequence satis⊂es 
 2287  the condition of De⊂nition R2. (|πFor if |εU|β0,|4U|β1,|4.|4
 2294  .|4. |πis such a sequence, take |εx|β0|4α=↓|4U|β0.)|'
 2301  !|9|7|πTherefore if R1 is too weak a de_nition, 
 2309  R2 is certainly too strong. The ``right'' de_nition 
 2317  must be less strict than R2. We have not really 
 2327  shown that R1 is too weak, however, so let us 
 2337  continue to attack it some more. As mentioned 
 2345  above, an |¬X-distributed sequence of |εrational 
 2351  |πnumbers has been constructed. (Indeed, this 
 2357  is not so surprising: see exercise 18.) Almost 
 2365  all real numbers are irrational; perhaps we should 
 2373  insist that|'{A9}Pr(|εU|βn |πis rational)|4α=↓|40|;
 2378  {A9}for a random sequence.|'!|9|7Note that the 
 2385  de_nition of equidistribution says that Pr(|εu|4|¬E|4U|βn|4|
 2390  ¬W|4v)|4α=↓|4v|4α_↓|4u. |πThere is an obvious 
 2395  way to generalize this de_nition, using measure 
 2402  theory: ::If |εS|4|↔Y|4[0,|41) |πis a set of 
 2409  measure |ε|≤m, |πthen|'{A9}Pr(|εU|βn|4|¬A|4S)|4α=↓|4|≤m,|J!(
 2412  27)|;{A9}|πfor all random sequences |↔b|εU|βn|↔v.'' 
 2418  |πIn particular, if |εS |πis the set of rationals, 
 2427  it has measure zero, so no sequence of rational 
 2436  numbers is equi|-distributed in this generalized 
 2442  sense. It is reasonable to expect that Theorem 
 2450  B could be extended to Lebesgue integration instead 
 2458  of Riemann integration, if property (27) is stipulated. 
 2466  However, once again we _nd that de_nition (27) 
 2474  is too strict, for |εno |πsequence satis_es that 
 2482  property*3 If |εU|β0,|4U|β1,|4.|4.|4. |πis any 
 2487  sequence, the set |εS|4α=↓|4|¬TU|β0,|4U|β1,|4.|4.|4.|¬Y 
 2491  |πis of measure zero, yet Pr(|εU|βn|4|¬A|4S)|4α=↓|41. 
 2497  |πThus, by the force of the same argument we 
 2506  used to exclude rationals from random sequences, 
 2513  we can exclude all random sequences.|'!|9|7So 
 2520  far De_nition R1 has proved to be defensible. 
 2528  There are, however, some quite valid objections 
 2535  to it. For example, if we have a random sequence 
 2545  in the intuitive sense, the in_nite subsequence|'
 2552  {A9}|εU|β0, U|β1, U|β4, U|β9, U|βn|l2,|4.|4.|4.|J!(28)|;
 2557  {A9}|πshould also be a random sequence. This 
 2564  is not always true for an |¬X-distributed sequence. 
 2572  (In fact, if we take any |¬X-distributed sequence 
 2580  and set |εU|βn|l2|4|¬L|40 |πfor all |εn, |πthe 
 2587  counts |ε|≤n|βk(n) |πwhich appear in the test 
 2594  of |εk-|πdistributivity are changed by at most 
 2601  |¬H|v4|εn|), |πso the limits of the ratios |ε|≤n|βk(n)/n 
 2609  |πremain unchanged.) Therefore R1 de_nitely fails 
 2615  to satisfy this randomness criterion.|'!|9|7Perhaps 
 2621  we should strengthen R1 as follows:|'{A12}|≡D|≡e|≡_|≡n|≡i|≡t
 2627  |≡i|≡o|≡n |≡R|≡3|≡.|9|4|εA [0,|41) sequence is 
 2632  said to be ``random'' if every in⊂nite subsequence 
 2640  is |¬X-distributed.|'{A12}|πBut once again we 
 2646  _nd this de_nition is too strict. If |↔b|εU|βn|↔v 
 2654  |πis any equi|-distributed sequence, it has a 
 2661  monotonic subsequence with |εU|βs|m0|4|¬W|4U|βs|m1|4|¬W|4U|β
 2664  s|m2|4|¬W|4αo↓|4αo↓|4αo↓|4.|'!|9|7|πThe secret 
 2667  is to restrict the subsequences so that they 
 2675  could be de_ned by a man who does not look at 
 2686  |εU|βn |πbefore he decides whether or not it 
 2694  is to be in the subsequence. The following de_nition 
 2703  now suggests itself:|'{A12}|≡D|≡e≡_|≡n|≡i|≡t|≡i|≡o|≡n 
 2707  |≡R|≡4|≡.|9|4|εA [0,|41) sequence |↔bU|βn|↔v 
 2711  is said to be ``random'' if, for every e∩ective 
 2720  algorithm which speci⊂es an in⊂nite sequence 
 2726  of distinct nonnegative integers s|βn for n|4|¬R|40, 
 2733  the subsequence U|βs|m0,|4U|βs|m1,|4.|4.|4. corresponding 
 2737  to this algorithm is |¬X-distributed.|'{A12}|π!|9|7The 
 2743  algorithms referred to in this de_nition are 
 2750  e=ective procedures which compute |εs|βn, |πgiven 
 2756  |εn. (|πSee Section 1.1.) Thus, for example, 
 2763  the sequence |↔b|ε|≤p|gn|4|πmod|41|↔v will |εnot 
 2768  |πsatisfy R4, since it is either not equidistributed 
 2776  or there is an e=ective algorithm which determines 
 2784  an in_nite subsequence |εs|βn |πwith (|ε|≤p|gs|r0|4|πmod|41)
 2789  |4|¬W|4(|ε|≤p|gs|r1|4|πmod|41)|4|¬W|4αo↓|4αo↓|4αo↓|4. 
 2790  Similarly, |εno explicitly de⊂ned sequence can 
 2796  satisfy De⊂nition R|*/|↔M; |\|πthis is appropriate, 
 2802  if we agree that no explicitly de_ned sequence 
 2810  can really be random. It is quite likely, however, 
 2819  that the sequence (|ε|≤u|gn|4|πmod|41|↔v will 
 2824  satisfy De_nition R4, for almost all real numbers 
 2832  |ε|≤u|4|¬Q|41; |πthis is no contradiction, since 
 2838  almost all |ε|≤u |πare uncomputable by algorithms. 
 2845  The following facts are known, for example: (i) 
 2853  The sequence |↔b|ε|≤u|gn|4|πmod|41|↔v satis_es 
 2857  De_nition R4 for almost all real |ε|≤u|4|¬Q|41, 
 2864  |πif ``|¬X-distributed'' is replaced by ``1-distributed.'' 
 2870  This theorem was proved by J. F. Koksma, |εCompositio 
 2879  Mathematica |π|≡2 (1935), 250<258. (ii) The particular 
 2886  sequence |↔b|ε|≤u|gs|g(|gn|g)|4|πmod|41|↔v is 
 2889  |¬X-distributed for almost all real |ε|≤u|4|¬Q|41, 
 2895  |πif |↔b|εs(n)|↔v |πis a sequence of integers 
 2902  for which |εs(n|4α+↓|41)|4α_↓|4s(n)|4|¬M|4|¬X 
 2905  |πas |εn|4|¬M|4|¬X. |πFor example, we could have 
 2912  |εs(n)|4α=↓|4n|g2, |πor |εs(n)|4α=↓|4|"ln|4|πlog|4|εn|↔L.|'
 2915  !|9|7|πDe_nition R4 is much stronger than De_nition 
 2922  R1; but it is still reasonable to claim that 
 2931  De_nition R4 is too weak. For example, let |↔b|εU|βn|↔v 
 2940  |πbe a truly random sequence, and de_ne the subsequence 
 2949  |↔b|εU|βs|mn|↔v |πby the following rules: |εs|β0|4α=↓|40, 
 2955  |πand (for |εn|4|¬Q|4O) s|βn |πis the smallest 
 2962  integer |→|¬R|εn |πfor which |εU|βs|mn|βα_↓|β1, 
 2967  U|βs|mn|βα_↓|β2,|4.|4.|4.|4, U|βs|mn|βα_↓|βn 
 2969  |πare all less than |f1|d32|). Thus we are considering 
 2978  the subsequence of values following the _rst 
 2985  consecutive run of |εn |πvalues less than |f1|d32|). 
 2993  Suppose that ``|εU|βn|4|¬W|4|f1|d32|)'' |πcorresponds 
 2997  to the value ``heads'' in the ⊗ipping of a coin. 
 3007  Gamblers tend to feel that a long run of ``heads'' 
 3017  makes the opposite condition, ``tails,'' more 
 3023  probable, assuming a true coin is being used; 
 3031  and the subsequence |ε|↔bU|βs|mn|↔v |πjust de_ned 
 3037  corresponds to a gambling system for a man who 
 3046  places his |εn|πth bet on the coin toss following 
 3055  the _rst run of |εn |πconsecutive ``heads.'' 
 3062  The gambler may think that Pr(|εU|βs|mn|4|¬R|4|f1|d32|)) 
 3068  |πis more than |f1|d32|), but of course in a 
 3077  truly random sequence, |ε|↔bU|βs|mn|↔v |πwill 
 3082  be completely random. No gambling system will 
 3089  ever able to beat the odds*3 De_nition R4 says 
 3098  nothing about subsequences formed according to 
 3104  such a gambling system, and so apparently we 
 3112  need something more.|'!|9|7Let us de_ne a ``subsequence 
 3120  rule'' |λR as an in_nite sequence of functions 
 3128  |ε|↔bf|βn(x|β1,|4.|4.|4.|4,|4x|βn)|↔v |πwhere, 
 3130  for |εn|4|¬R|40, f|βn |πis a function of |εn 
 3138  |πvariables, and the value of |εf|βn(x|β1,|4.|4.|4.|4,|4x|βn
 3143  ) |πis either 0 or 1. Here |εx|β1,|4.|4.|4.|4,|4x|βn 
 3151  |πare elements of some set |εS. (|πThus, in particular, 
 3160  |εf|β0 |πis a constant function, either 0 or 
 3168  1.) A subsequence rule |λR de_nes a subsequence 
 3176  of any in_nite sequence |↔b|εX|βn|↔v |πof elements 
 3183  of |εS |πas follows: |εThe n|πth |εterm X|βn 
 3191  is in the subsequence |↔bX|βn|↔v|λR if and only 
 3199  if f|βn(X|β0, X|β1,|4.|4.|4.|4,|4X|βn|βα_↓|β1)|4α=↓|41. 
 3202  |πNote that the subsequence |ε|↔bX|βn|↔v|λR |πthus 
 3208  de_ned is not necessarily in_nite, and it may 
 3216  in fact be the null subsequence.|'!|9|7The ``gambler's 
 3224  subsequence'' which was described above corresponds 
 3230  to the following subsequence rule: ``|εf|β0|4α=↓|41; 
 3236  |πand for |εn|4|¬Q|40, f|βn(x|β1,|4.|4.|4.|4,|4x|βn)|4α=↓|41
 3239   |πif and only if there is some |εk,|40|4|¬W|4k|4|¬E|4n, 
 3248  |πsuch that |εx|βm|4|¬W|4|f1|d32|), x|βm|βα_↓|β1|4|¬W|4|f1|d
 3251  32|),|4.|4.|4.|4, x|βm|βα_↓|βk|βα+↓|β1|4|¬W|4|f1|d32|), 
 3253  |πwhen |εm|4α=↓|4n |πbut not when |εk|4|¬E|4m|4|¬W|4n.''|'
 3259  !|9|7|πA subsequence rule |λR is said to be |εcomputable 
 3268  |πif there is an e=ective algorithm which determines 
 3276  the value of |εf|βn(x|β1,|4.|4.|4.|4,|4x|βn), 
 3280  |πwhen |εn,|4x|β1,|4.|4.|4.|4,|4x|βn |πare given 
 3284  as input. In a de_nition of randomness, we should 
 3293  restrict ourselves to computable subsequence 
 3298  rules, or else we obtain a de_nition like R3 
 3307  above, which is too strong. E=ective algorithms 
 3314  cannot deal nicely with arbitrary real numbers 
 3321  as inputs; for example, if a real number |εx 
 3330  |πis speci_ed by an in_nite radix-10 expansion, 
 3337  there is no algorithm to determine if |εx  |πis 
 3347  |→|¬W|f1|d33|) or not, since all digits of the 
 3355  number 0.333|4.|4.|4. would have to be examined. 
 3362  Therefore computable subsequence rules do not 
 3368  apply to all [0,|41) sequences, and it is convenient 
 3377  to base our next de_nition on |εb-|πary sequences:|'
 3385  {A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|≡n |≡R|≡5|≡.|9|4|εA 
 3387  b-ary sequence is said to be ``random'' if every 
 3396  in⊂nite subsequence de⊂ned by a computable subsequence 
 3403  rule is |*/|↔O|\-distributed.|'!|9|7A [0,|41) 
 3408  sequence |↔bU|βn|↔v is said to be ``random'' 
 3415  if the b-ary sequence |↔b|"lbU|βn|"L|↔v is ``random'' 
 3422  for all integers b|4|¬R|42.|'|Hu{U0}{H10L12M29}|πW58320#Comp
folio 206 galley 5
 3426  uter Programming!(Knuth/Addison-Wesley)!f.|4206!ch.|43!g.|45
 3427  d|'{A6}{A6}!|9|7Note that De_nition R5 says only 
 3434  ``1-distributed,'' not ``|¬X-distributed.'' It 
 3438  is interesting to note that this may be done 
 3447  without loss of generality. for, we may de_ne 
 3455  an obviously computable subsequence rule |λR(|εa|β1|4.|4.|4.
 3460  |4a|βk) |πas follows for any |εb-|πary number 
 3467  |εa|β1|4.|4.|4.|4a|βk: |πLet |εf|βn(x|β1,|4.|4.|4.|4,|4x|βn)
 3469  |4α=↓|41 |πif and only if |εn|4|¬R|4k|4α_↓|41 
 3475  |πand |εx|βn|βα_↓|βk|βα+↓|β1|4α=↓|4a|β1,|4.|4.|4.|4, 
 3477  x|βn|βα_↓|β1|4α=↓|4a|βk|βα_↓|β1, x|βn|4α=↓|4a|βk. 
 3479  |πNow if |ε|↔bX|βn|↔v |πis a |εk-|πdistributed 
 3485  |εb-|πary sequence, this rule |λR(|εa|β1|4.|4.|4.|4a|βk)#|πw
 3489  hich selects the subsequence consisting of those 
 3496  terms just following an occurrence of |εa|β1|4.|4.|4.|4a|βk#
 3502  |πde_nes an in_nite subsequence; and if this 
 3509  subsequence is 1-distributed, each of the |ε(k|4α+↓|41)-|πtu
 3515  ples |εa|β1|4.|4.|4.|4a|βka|βk|βα+↓|β1 |πfor 
 3518  0|4|¬E|4|εa|βk|βα+↓|β1|4|¬W|4b |πoccurs with 
 3521  probability |ε1/b|gk|gα+↓|g1 |πin |↔b|εX|βn|↔v. 
 3525  |πThus we can prove that a sequence satisfying 
 3533  De_nition R5 is |εk-|πdistributed for all |εk, 
 3540  |πby induction on |εk. |πSimilarly, by considering 
 3547  the ``composition'' of subsequence rules#if |λR|β1 
 3553  de_nes an in_nite subsequence |↔b|εX|βn|↔v|λR|β1, 
 3558  |πthen we can de_ne |λR|β1|λR|β2 to be the subsequence 
 3567  rule for which |↔b|εX|βn|↔v|λR|β1|λR|β2|4α=↓|4(|↔bX|βn|↔v|λR
 3570  |β1)|λR|β2#|πwe _nd that all subsequences considered 
 3576  in De_nition R5 are |¬X-distributed. (See exercise 
 3583  32.)|'!|9|7The fact that |¬X-distribution comes 
 3589  out of De_nition R5 as a very special case is 
 3599  encouraging, and it is a good indication that 
 3607  we may at last have found the de_nition of randomness 
 3617  which we have been seeking. But alas, there still 
 3626  is a problem*3 It is not clear that sequences 
 3635  satisfying De_nition R5 must satisfy De_nition 
 3641  4. The ``computable subsequence rules'' we have 
 3648  just speci_ed always enumerate subsequences |↔b|εX|βs|mn|↔v 
 3654  |πfor which |εs|β0|4|¬W|4s|β1|4|¬W|4αo↓|4αo↓|4αo↓|4, 
 3657  |πbut |ε|↔bs|βn|↔v |πdoes not have to be monotone 
 3665  in R4; it must only satisfy the condition |εs|βn|4|=|↔6α=↓|4
 3673  s|βm |πfor |εn|4|=|↔6α=↓|4m.|'!|9|7|πTo meet 
 3678  this objection, we may combine De_nitions R4 
 3685  and R5 as follows:|'{A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|≡n 
 3690  |≡R|≡6|≡.|9|4|εA b-ary sequence |↔bX|βn|↔v is 
 3695  said to be ``random'' if, for every e∩ective 
 3703  algorithm which speci⊂es an in⊂nite sequence 
 3709  of distinct nonnegative integers |↔bs|βn|↔v as 
 3715  a function of n and the values of X|βs|m0,|4.|4.|4.|4,|4X|βs
 3723  |mn|mα_↓|m1, the subsequence |↔bX|βs|mn|↔v corresponding 
 3728  to this algorithm is ``random'' in the sense 
 3736  of De⊂nition R|*/|↔C|\.|'!|9|7A [0,|41) sequence 
 3742  |↔bU|βn|↔v is said to be ``random'' if the b-ary 
 3751  sequence |↔b|"lbU|βn|"L|↔v is ``random'' for 
 3756  all integers b|4|¬R|42.|'{A12}|π!|9|7The author 
 3761  contendsα/↓ that this de_nition surely meets 
 3767  all reasonable philosophical requirements for 
 3772  randomness, and so it provides an answer to the 
 3781  principal question posed in this section.|'{A2}######|'
 3788  {H8L10}!α/↓|4At least, he felt that way when 
 3795  originally preparing the material for this section.|'
 3802  {A12}{H10L12}|≡D|≡.|9|≡E|≡x|≡i|≡s|≡t|≡e|≡n|≡c|≡e 
 3803  |≡o|≡f |≡r|≡a|≡n|≡d|≡o|≡m |≡s|≡e|≡q|≡u|≡e|≡n|≡c|≡e|≡s|≡.|9|4
 3805  We have seen that De_nition R3 is too strong, 
 3814  in the sense that no sequences could exist satisfying 
 3823  that de_nition; and the formulation of De_nitions 
 3830  R4, R5, and R6 above was carried out in an attempt 
 3841  to recapture the essential characteristics of 
 3847  De_nition R3. In order to show that De_nition 
 3855  R6 is not overly restrictive, it is still necessary 
 3864  for us to prove that sequences satisfying all 
 3872  these conditions exist. Intuitively, we feel 
 3878  quite sure that such sequences exist, because 
 3885  we believe that a truly random sequence exists 
 3893  and satis_es De_nition R6; but a proof is really 
 3902  necessary to show that the de_nition is consistent.|'
 3910  !|9|7An interesting method for constructing sequences 
 3916  satisfying De_nition R5 has been given by A. 
 3924  Wald. The construction starts with a very simple 
 3932  1-distributed sequence:|'{A12}|≡L|≡e|≡m|≡m|≡a 
 3935  |≡T|≡.|9|4|εLet the sequence of real numbers 
 3941  |↔b|εV|βn|↔v be de⊂ned in terms of the binary 
 3949  system as follows|*/:|\|'V|β0|4|∂α=↓|40,!!V|β1|4α=↓|4.1,!!V|β
 3952  2|4α=↓|4.01,!!V|β3|4α=↓|4.11,!!V|β4|4α=↓|4.001,!!.|4.|4.|;
 3953  {A4}| V|βn|4|Lα=↓|4.c|βr|4.|4.|4.|4c|β11!!|πif!!|εn|4α=↓|42|
 3953  gr|4α+↓|4c|β12|gr|gα_↓|g1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|βr.|J!
 3953  (29)>{A9}Let I|βb|m1|1|β.|1|β.|1|β.|1b|mr denote 
 3957  the set of all real numbers in [0,|41) whose 
 3966  binary representation begins with 0.b|β1|4.|4.|4.|4b|βr|*/;|\
 3970   thus|'{A9}I|ur|)b|β1|1|1.|1|1.|1|1.|1|1b|βr|)|4α=↓|4[0.b|β1
 3972  |4.|4.|4.|4b|βr, o.b|β1|4.|4.|4.|4b|βr|4α+↓|42|gα_↓|gr).|J!(
 3973  30)|;{A9}Then if |≤n(n) denotes the number of 
 3981  V|βk in I|βb|m1|1|β.|1|β.|1|β.|1|βb|mr for 0|4|¬E|4k|4|¬W|4n
 3985  , we have|'{A9}|¬G|≤n(n)/n|4α_↓|42|gα_↓|gr|¬G|4|¬E|41/n.|J!(
 3988  31)|;{A9}Proof.|9|4|πSince |ε|≤n(n) |πis the 
 3993  number of |εk |πfor which |εk|4|πmod|4|ε2|gr|4α=↓|4b|βr|4.|4
 3998  .|4.|4b|β1, |πwe have |ε|≤n(n)|4α=↓|4t |πor |εt|4α+↓|41 
 4004  |πwhen |"l|εn/2|gr|"L|4α=↓|4t. |πHence |¬G|ε|≤n(n)|4α_↓|4n/2
 4007  |gr|¬G|4|¬E|41.|'{A12}!|9|7|πIt follows from 
 4011  (31) that the sequence |↔b|"l|ε2|grV|βn|"L|↔v 
 4016  |πis an equidistributed 2|ε|gr-|πary sequence; 
 4021  hence by Theorem A, |↔b|εV|βn|↔v |πis an equidistributed 
 4029  [0,|41) sequence. Indeed, it is pretty clear 
 4036  that |↔b|εV|βn|↔v |πis about as equidistributed 
 4042  as a [0,|41) sequence can be*3 (For further discussion 
 4051  of this and related sequences, see J. C. van 
 4060  der Corput, |εProc. Koninklijke Nederlandse Akademie 
 4066  van Wetenschappen |≡3|≡8 (1935), 813<821, 1058<1066; 
 4072  |πJ. H. Halton, |εNumerische Mathematik |π|≡2 
 4078  (1960), 84<90, 196.)|'!|9|7Now let |λR|β1,|4|λR|β2,|4.|4.|4.
 4083   be in_nitely many subsequence rules; we would 
 4091  like to _nd a sequence |↔b|εU|βn|↔v |πfor which 
 4099  all the in_nite subsequences |↔b|εU|βn|↔v|λR|βj 
 4104  |πare equidistributed.|'{A12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m 
 4107  |≡W (|εWald sequence).|9|4|πGiven an in_nite 
 4112  set of subsequence rules |λR|β1,|4|λR|β2,|4.|4.|4.|4, 
 4117  which de_ne subsequences of [0,|41) sequences 
 4123  of |εrational |πnumbers, this procedure de_nes 
 4129  a [0,|41) sequence |↔b|εU|βn|↔v. |πThe computation 
 4135  involves in_nitely many auxiliary variables |εC[a|β1,|4.|4.|
 4140  4.|4,|4a|βr] |πwhere |εr|4|¬R|41 |πand where 
 4145  |εa|βj|4α=↓|40 |πor 1 for 1|4|¬E|4|εj|4|¬E|4r. 
 4150  |πThese variables are initially all zero.|'{A3}|π|≡W|≡1|≡.|9
 4156  [Initialize |εn.] |πSet |εn|4|¬L|40.|'{A3}|π|≡W|≡2|≡.|9[Init
 4160  ialize |εr.] |πSet |εr|4|¬L|41.|'{A3}|π|≡W|≡3|≡.|9[Test 
 4165  |λR|ε|βr.] |πIf the element |εU|βn |πis to be 
 4173  in the subsequence de_ned by |λR|ε|βr, |πbased 
 4180  on the values of |εU|βk |πfor 0|4|¬E|4|εk|4|¬W|4n, 
 4187  |πset |εa|βr|4|¬L|41; |πotherwise set |εa|βr|4|¬L|40.|'
 4192  {A3}|π|≡W|≡4|≡.|9[|εB[a|β1,|4.|4.|4.|4,|4a|βr] 
 4193  |πfull?] If |εC[a|β1,|4.|4.|4.|4,|4a|βr]|4|¬W|43|4αo↓|44|gr|
 4195  gα_↓|g1, |πgo to W6.|'{A3}|≡W|≡5|≡.|9[Increase 
 4200  |εr.] |πSet |εr|4|¬L|4r|4α+↓|41 |πand return 
 4205  to W3.|'{A3}|≡W|≡6|≡.|9[Set |εU|βn.] |πIncrease 
 4210  |εC[a|β1,|4.|4.|4.|4,|4a|βr] |πby 1 and let |εk 
 4216  |πbe the new value of |εC[a|β1,|4.|4.|4.|4,|4a|βr]. 
 4222  |πSet |εU|βn|4|¬L|4V|βk, |πwhere |εV|βk |πis 
 4227  de_ned in Lemma T above.|'{A3}|≡W|≡7|≡.|9[Advance 
 4233  |εn.] |πIncrease |εn |πby 1 and return to W2.|'
 4242  {A3}{A9}!|9|7Strictly speaking, this is not an 
 4248  algorithm, since it doesn't terminate; it would 
 4255  of course be easy to modify the procedure to 
 4264  stop when |εn |πreaches a given value. The reader 
 4273  will _nd it easier to grasp the idea of the construction 
 4284  if he tries it by hand, replacing the number 
 4293  3|4αo↓|44|ε|gr|gα_↓|g1 |πof step W4 by 2|ε|gr 
 4299  |πduring this experiment.|'!|9|7Algorithm W is 
 4305  not meant to be a practical source of random 
 4314  numbers; it is intended to serve only a theoretical 
 4323  purpose:|'{A12}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡W|≡.|9|4|εLet 
 4326  U|βn be the sequence of rational numbers de⊂ned 
 4334  by Algorithm W, and let k be a positive integer. 
 4344  If the subsequence |↔bU|βn|↔v|λR|βk is in⊂nite, 
 4350  it is |*/|↔O|\-distributed.|'{A12}Proof.|9|4|πLet 
 4354  |εA[a|β1,|4.|4.|4.|4,|4a|βr] |πdenote the (possibly 
 4358  empty) subsequence of |↔b|εU|βn|↔v |πcontaining 
 4363  precisely those elements |εU|βn |πwhich, for 
 4369  all |εj, 1|4|¬E|4j|4|¬E|4r, |πbelong to subsequence 
 4375  |ε|↔bU|βn|↔v|λR|βj |πif |εa|βj|4α=↓|41 |πand 
 4379  do not belong to subsequence |↔b|εU|βn|↔v|λR|βj 
 4385  |πif |εa|βj|4α=↓|40.|'!|9|7|πIt su∃ces to prove, 
 4391  for all |εr|4|¬R|41 |πand all pairs of binary 
 4399  numbers |εa|β1|4.|4.|4.|4a|βr |πand |εb|β1|4.|4.|4.|4b|βr, 
 4403  |πthat Pr(|εU|βn|4|¬A|4I|βb|m1|1|β.|1|β.|1|β.|1|βb|mr)≥|4α=↓
 4404  |42|gα_↓|gr |πwith respect to the subsequence 
 4410  |εA[a|β1,|4.|4.|4.|4,|4a|βr], |πwhenever the 
 4413  latter is in_nite. [See Eq. (30).] For if |εr|4|¬R|4k, 
 4422  |πthe in_nite sequence |↔b|εU|βn|↔v|λR|βk |πis 
 4427  the _nite union of the disjoint subsequences 
 4434  |εA[a|β1,|4.|4.|4.|4,|4a|βr] |πfor |εa|βk|4α=↓|41 
 4437  |πand |εa|βj|4α=↓|40 |πor 1 for 1|4|¬E|4|εj|4|¬E|4r, 
 4443  j|4|=|↔6α=↓|4k; |πand it follows that Pr(|εU|βn|4|¬A|4I|βb|m
 4448  1|1|β.|1|β.|1|β.|1|βb|mr)|4α=↓|42|gα_↓|gr |πwith 
 4450  respect to |ε|↔bU|βn|↔v|λR|βk. (|πSee exercise 
 4455  33.) This is enough to show that the sequence 
 4464  is 1-distributed, by Theorem A.|'|Hu{U0}{H10L12M29}|πW58320#
folio 209 galley 6
 4469  Computer Programming!(Knuth/Addison-Wesley)!f.|4209!ch.|43!g
 4470  .|46d|'{A6}!|9|7Let |εB[a|β1,|4.|4.|4.|4,|4a|βr] 
 4473  |πdenote the subsequence of |ε|↔bU|βn|↔v |πwhich 
 4479  consists of the values for those |εn |πin which 
 4488  |εC[a|β1,|4.|4.|4.|4,|4a|βr] |πis increased by 
 4492  one in step W6 of the algorithm. By the algorithm, 
 4502  |εB[a|β1,|4.|4.|4.|4,|4a|βr] |πis a _nite sequence 
 4507  with at most 3|4αo↓|44|ε|gr|gα_↓|g1 |πelements. 
 4512  All but a _nite number of the members of |εA[a|β1,|4.|4.|4.|
 4521  4,|4a|βr] |πcome from the subsequences |εB[a|β1,|4.|4.|4.|4,
 4526  |4a|βr,|4.|4.|4.|4,|4a|βt], |πwhere |εa|βj|4α=↓|40 
 4529  |πor 1 for |εr|4|¬W|4j|4|¬E|4t.|'!|9|7|πNow assume 
 4535  that |εA[a|β1,|4.|4.|4.|4,|4a|βr] |πis in_nite, 
 4539  and let |εA[a|β1,|4.|4.|4.|4,|4a|βr]|4α=↓|4|↔bU|βs|mn|↔v 
 4542  |πwhere |εs|β0|4|¬W|4s|β1|4|¬W|4s|β2|4|¬E|4αo↓|4αo↓|4αo↓|4. 
 4544  |πIf |εN |πis a large integer, with |ε4|gr|4|¬E|44|gq|4|¬W|4
 4551  N|4|¬E|44|gq|gα+↓|g1, |πit follows that the number 
 4557  of values of |εk|4|¬W|4N |πfor which |εU|βs|mk 
 4564  |πis in |εI|βb|m1|1|β.|1|β.|1|β.|1|βb|mr |πis 
 4568  (except for _nitely many elements at the beginning 
 4576  of the subsequence)|'{A9}|ε|≤n(N)|4α=↓|4|≤n(N|β1)|4α+↓|4αo↓|
 4579  4αo↓|4αo↓|4α+↓|4|≤n(N|βm).|;{A9}|πHere |εm |πis 
 4583  the number of subsequences |εB[a|β1,|4.|4.|4.|4,|4a|βt] 
 4588  |πlisted above in which |εU|βs|mk |πappears for 
 4595  some |εk|4|¬W|4N; N|βj |πis the number of values 
 4603  of |εk |πwith |εU|βs|mk |πin the corresponding 
 4610  subsequence; and |ε|≤n(N|βj) |πis the number 
 4616  of such values which are also in |εI|βb|m1|1|β.|1|β.|1|β.|1|
 4623  βb|mr. |πTherefore by Lemma T,|'{A9}|ε|¬G|≤n(N)|4α_↓|42|gα_↓
 4628  |grN|¬G|4|∂α=↓|4|¬G|≤n(N|β1)|4α_↓|42|gα_↓|grN|β1|4α+↓|4αo↓|4
 4628  αo↓|4αo↓|4α+↓|4|≤n(N|βm)|4α_↓|42|gα_↓|grN|βm|¬G|9|;
 4629  {A4}|L|¬E|4|¬G|≤n(N|β1)|4α_↓|42|gα_↓|grN|β1|¬G|4α+↓|4αo↓|4αo
 4629  ↓|4αo↓|4α+↓|4|¬G|≤n(N|βm)|4α_↓|42|gα_↓|grN|βm|¬G>
 4630  {A4}|L|¬E|4m|4|¬E|41|4α+↓|42|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|42|gq|
 4630  gα_↓|gr|gα+↓|g1|4|¬W|42|gq|gα+↓|g1.>{A9}|πThe 
 4632  inequality on |εm |πfollows here from the fact 
 4640  that, by our choice of |εN, U|βs|mN |πis in |εB[a|β1,|4.|4.|
 4649  4.|4,|4a|βt] |πfor some |εt|4|¬E|4q|4α+↓|41.|'
 4653  !|9|7|πTherefore|'{A3}|ε|¬G|≤n(N)/N|4α_↓|42|gα_↓|gr|¬G|4|¬E|
 4654  42|gq|gα+↓|g1/N|4|¬W|42/|¬H|v4N|).!|9|;{A9}!|9|7|πTo 
 4656  show _nally that sequences satisfying De_nition 
 4662  R5 exist, we note _rst that if |ε|↔bU|βn|↔v |πis 
 4671  a [0,|41) sequence of rational numbers and if 
 4679  |λR is a computable subsequence rule for a |εb-|πary 
 4688  sequence, we can make |λR into a computable subsequence 
 4697  rule rule |λR|¬S |πfor |ε|¬BU|βn|¬V |πby letting 
 4704  |εf|ur|↔0|)n|)(x|β1,|4.|4.|4.|4,|4x|βn) |πin 
 4706  |λR|¬S equal |εf|βn(|"lbx|β1|"L,|4.|4.|4.|4, 
 4709  |"lbx|βn|"L) |πin |λR. If the sequence |ε|↔bU|βn|↔v|λR|¬S 
 4716  |πis equidistributed, so is the sequence |↔b|"l|εbU|βn|"L|↔v
 4722  |λR. |πNow the set of all computable subsequence 
 4730  rules for |εb-|πary sequences, for all values 
 4737  of |εb, |πis countable (since only countably 
 4744  many e=ective algorithms are possible), so they 
 4751  may be listed in some sequence |λR|β1,|4|λR|β2,|4.|4.|4.|4; 
 4758  therefore Algorithm W de_nes a [0,|41) sequence 
 4765  which is random in the sense of De_nition R5.|'
 4774  !|9|7This brings us to a somewhat paradoxical 
 4781  situation. As we mentioned earlier, no e=ective 
 4788  algorithm can de_ne a sequence which satis_es 
 4795  De_nition R4, and for the same reason there is 
 4804  no e=ective algorithm which de_nes a sequence 
 4811  satisfying De_nition R5. A proof of the existence 
 4819  of such random sequences is necessarily nonconstructive; 
 4826  how then can Algorithm W construct such a sequence?|'
 4835  !|9|7There is no contradiction here; we have 
 4842  merely stumbled on the fact that the set of all 
 4852  e=ective algorithms cannot be enumerated by an 
 4859  e=ective algorithm. In other words, there is 
 4866  no e=ective algorithm to select the |εj|πth computable 
 4874  subsequence rule |ε|λR|βj; |πthis happens because 
 4880  there is no e=ective algorithm to determine if 
 4888  a computational method ever terminates. (We shall 
 4895  return to this topic in Chapter 11.) Important 
 4903  large classes of algorithms |εcan |πbe systematically 
 4910  enumerated; thus, for example, Algorithm W shows 
 4917  that is possible to construct, with an e=ective 
 4925  algorithm, a sequence which satis_es De_nition 
 4931  R5 if we restrict consideration to subsequence 
 4938  rules which are ``primitive recursive.''|'!|9|7By 
 4944  modifying step W6 of Algorithm W, so that it 
 4953  sets |εU|βn|4|¬L|4V|βk|βα+↓|βt |πinstead of |εV|βk, 
 4958  |πwhere |εt |πis any nonnegative integer depending 
 4965  on |εa|β1,|4.|4.|4.|4,|4a|βr, |πwe can show that 
 4971  are |εuncountably |πmany [0,|41) sequences satisfying 
 4977  De_nition R5.|'!|9|7The following theorem shows 
 4983  still another way to prove the existence of uncountably 
 4992  many random sequences, using a less direct argument 
 5000  based on measure theory, even if the strong de_nition 
 5009  R6 is used:|'{A12}|≡T|≡h|≡e|≡o|≡r|≡e|≡m |≡M|≡.|9|4|εLet 
 5014  the real number x,|40|4|¬E|4x|4|¬W|41, correspond 
 5019  to the binary sequence |↔bX|βn|↔v if the binary 
 5027  representation of x is 0.X|β0X|β1|4.|4.|4.|4. 
 5032  Under this correspondence, almost all x correspond 
 5039  to binary sequences which are random in the sense 
 5048  of De⊂nition R|*/|↔o|\. (|πIn other words, the 
 5055  set of all real |εx |πwhich correspond to a binary 
 5065  sequence which is nonrandom by De_nition R6 has 
 5073  measure zero.)|'{A12}|εProof.|9|4|πLet |λS be 
 5078  an e=ective algorithm which determines an in_nite 
 5085  sequence of distinct nonnegative integers |↔b|εs|βn|↔v, 
 5091  |πwhere the choice of |εs|βn |πdepends only on 
 5099  |εn |πand |εX|βs|mk |πfor 0|4|¬E|4|εk|4|¬W|4n; 
 5104  |πand let |λR be a computable subsequence rule. 
 5112  Then any binary sequence |ε|↔bX|βn|↔v |πleads 
 5118  to a subsequence |ε|↔bX|βs|mn|↔v|λR, |πand De_nition 
 5124  R6 says this subsequence must either be _nite 
 5132  or 1-distributed. It su∃ces to prove that |εfor 
 5140  ⊂xed |λR and |λS the set N(|λr,|4|λS) of all 
 5149  real x corresponding to |↔bX|βn|↔v, such that 
 5156  |↔bX|βs|mn|↔v|λR is in⊂nite and not |*/|↔O|\-distributed, 
 5162  has measure zero. |πFor |εx |πhas a nonrandom 
 5170  binary representation if and only if |εx |πis 
 5178  in |↔e|4|εN(|λR,|4|λS), |πtaken over the countably 
 5184  many choices of |λR |πand |λS.|'!|9|7Therefore 
 5191  let |λR and |λS be _xed. Consider the set |εT(a|β1a|β2|4.|4.
 5200  |4.|4a|βr) |πde_ned for all binary numbers |εa|β1a|β2|4.|4.|
 5206  4.|4a|βr |πas the set of all |εx |πcorresponding 
 5214  to |ε|↔bX|βn|↔v, |πsuch that |ε|↔bX|βs|mn|↔v|λ9 
 5219  |πhas |ε|→|¬Rr |πelements whose _rst |εr |πelements 
 5226  are respectively equal to |εa|β1,|4a|β2,|4.|4.|4.|4,|4a|βr. 
 5231  |πOur _rst result is that|'{A9}|εT(a|β1a|β2|4.|4.|4.|4a|βr)!
 5236  !|πhas measure!!|ε|→|¬E2|gα_↓|gr.|J!(32)|;{A9}|πTo 
 5239  prove this, we start by observing that |εT(a|β1a|β2|4.|4.|4.
 5246  |4a|βr) |πis a measurable set: Each element of 
 5254  |εT(a|β1a|β2|4.|4.|4.|4a|βr) |πis a real number 
 5259  |εx|4α=↓|40.X|β0X|β1|4.|4.|4.|4|πfor which there 
 5262  exists an integer |εm |πsuch that algorithm |λS 
 5270  determines distinct values |εs|β0,|4s|β1,|4.|4.|4.|4,|4s|βm,
 5273   |πand rule |λR determines a subsequence of |εX|βs|m0,|4X|βs
 5281  |m1,|4.|4.|4.|4,|4X|βs|mm |πsuch that |εX|βs|mm 
 5285  |πis the |εr|πth element of this sequence. The 
 5293  set of all real |εy|4α=↓|40.Y|β0Y|β1|4.|4.|4. 
 5298  |πsuch that |εY|βs|mk |πfor 0|4|¬E|4|εk|4|¬E|4m 
 5303  |πalso belongs to |εT(a|β1a|β2|4.|4.|4.|4a|βr), 
 5307  |πand this is a measurable set consisting of 
 5315  the _nite union of dyadic subintervals |εI|βb|m1|1|β.|1|β.|1
 5321  |β.|1|mt. |πSince there are only countably many 
 5328  such dyadic intervals, we see that |εT(a|β1a|β2|4.|4.|4.|4a|
 5334  βr) |πis a countable union of dyadic intervals, 
 5342  and it is therefore measurable. Furthermore, 
 5348  this argument can be extended to show that the 
 5357  measure of |εT(a|β1|4.|4.|4.|4a|βr|βα_↓|β10) 
 5360  |πequals the measure of |εT(a|β1|4.|4.|4.|4a|βr|βα_↓|β11), 
 5365  |πsince the latter is a union of dyadic intervals 
 5374  obtained from the former by requiring that |εY|βs|mk|4α=↓|4X
 5381  |βs|mk |πfor |ε0|4|¬E|4k|4|¬W|4m |πand |εY|βs|mm|4|=|↔6α=↓|4
 5385  X|βs|mm. |πNow since|'{A9}|εT(a|β1|4.|4.|4.|4a|βr|βα_↓|β10)|
 5388  4|↔q|4T(a|β1|4.|4.|4.|4a|βr|βα_↓|β11)|4|↔Y|4T(a|β1|4.|4.|4.|
 5388  4a|βr|βα_↓|β1),|;{A9}|πthe measure of |εT(a|β1a|β2|4.|4.|4.|
 5392  4a|βr) |πis at most one-half the measure of |εT(a|β1|4.|4.|4
 5400  .|4a|βr|βα_↓|β1). |πThe inequality (32) follows 
 5405  by induction on |εr.|'!|9|7|πNow that (32) has 
 5413  been established, the remainder of the proof 
 5420  is essentially to show that the binary representations 
 5428  of almost all real numbers are equi|-distributed. 
 5435  The next few paragraphs constitute a rather ling 
 5443  but not di∃cult proof of this fact, and they 
 5452  serve to illustrate typical estimation techniques 
 5458  in mathematical{U0}{H10L12M29}|πW58320#Computer 
folio 212 galley 7
 5460  Programming!(Knuth/Addison-Wesley)!f.|4212!ch.|43!g.|47d|'
 5461  {A6}!|9|7For |εo|4|¬W|4|≤e|4|¬W|41, |πlet |εB(r,|4|≤e) 
 5465  |πbe |↔e|4|εT(a|β1|4.|4.|4.|4a|βr), |πwhere the 
 5469  union is taken over all binary numbers |εa|β1|4.|4.|4.|4a|βr
 5476   |πfor which the number |ε|≤n(r) |πof zeros among 
 5485  |εa|β1|4.|4.|4.|4a|βr |πsatis_es|'{A9}|ε|¬G|≤n(r)|4α_↓|4|f1|
 5487  d32|)r|¬G|4|¬R|41|4α+↓|4|≤er.|;{A9}|πThe number 
 5490  of such binary numbers is |εC(|εr,|4|≤e)|4α=↓|4|¬K|4(|fr|d3k
 5495  |)) |πsummed over the values of |εk |πwith |ε|¬Gk|4α_↓|4|f1|
 5503  d32|)r|¬G|4|¬R|41|4α+↓|4|≤er. |πA suitable estimate 
 5507  for the tail of the binomial distribution can 
 5515  be obtained by the following standard trick: 
 5522  Let |εx |πbe any positive number less than 1, 
 5531  and let |εs|4α=↓|4(|f1|d32|)|4α+↓|4|≤e)r. |πThen|'
 5535  {A9}|ε|↔k|uc|)k|¬Rs|)|1|1|↔a|(r|d5k|)|↔s|4|¬E|4|↔k|uc|)k|¬Rs
 5535  |)|1|1|↔a|(r|d5k|)|↔sx|gs|gα_↓|gk|4|¬E|4|↔k|uc|)k|¬R0|)|1|1|
 5535  ↔a|(r|d5k|)|↔sx|gs|gα_↓|gk|4α=↓|4x|g5|↔a1|4α+↓|4|(1|d2x|)|↔s
 5535  |gr.|;{A9}|πBy elementary calculus, the minimum 
 5541  value of |εx|gs(1|4α+↓|41/x)|gr |πoccurs when 
 5546  |εx|4α=↓|4r/s|4α_↓|41|4α=↓|4(1|4α_↓|42|≤e)/(1|4α+↓|42|≤e), 
 5547  |πand this value of |εx |πyields|'{A9}|ε|↔k|uc|)k|¬R(1/2α+↓|
 5553  ≤e)r|)|1|1|↔a|(r|d5k|)|↔s|4|¬E|4|↔a|(2|d2(1|4α+↓|42|≤e)|g1|g
 5553  /|g2|gα+↓|g|≤e(1|4α_↓|42|≤e)|g1|g/|g2|gα_↓|g|≤e|)|↔s|gr.|;
 5554  {A9}|πNow when |ε|≤e|4|¬W|4|f1|d32|) |πwe have|'
 5559  {A9}|ε(|f1|d32|)|4α+↓|4|≤e)|πln(1|4α+↓|4|ε2|≤e)|4α+↓|4(|f1|d
 5559  32|)|4α_↓|4|≤e)|πln(1|4α_↓|42|ε|≤e)|4α=↓|4|(1|d21|4αo↓|42|)|
 5559  4(2|≤e)|g2|4α+↓|4|(1|d23|4αo↓|44|)|4(2|≤e)|g4|4α+↓|4|(1|d25|
 5559  4αo↓|46|)|4(2|≤e)|g6|4α+↓|4αo↓|4αo↓|4αo↓|4|¬Q|42|≤e|g2,|;
 5560  {A9}|πhence the denominator in our estimate is 
 5567  larger than |εe|gα_↓|g2|g|≤e|i2. |πWe have proved 
 5573  that|'{A9}|ε|↔k|uc|)k|¬R(1/2α+↓|≤e)r|)|1|1|↔a|(r|d5k|)|↔s|4|
 5574  ¬W|42|gre|gα_↓|g2|g|≤e|i2r,!!|πfor all!!|εr|4|¬Q|40!!|πand!!
 5575  0|4|¬W|4|ε|≤e|4|¬W|4|f1|d32|).|J!(33)|;{A9}|πBut 
 5577  |εC(r,|4|≤e) |πis twice this left-hand quantity, 
 5583  hence by (32) and (33)|'{A9}|εB(r,|4|≤e)!!|πhas 
 5589  measure!!|ε|→|¬E2|gα_↓|grC(r,|4|≤e)|4|¬W|42e|gα_↓|g2|g|≤e|i2
 5589  |gr.|;{A9}|π!|9|7The next step is to de_ne|'{A9}|εB|¬S(r, 
 5597  |≤e)|4α=↓|4B(r, |≤e)|4|↔q|4B(r|4α+↓|41, |≤e)|4|↔q|4B(r|4α+↓|
 5599  42, |≤e)|4|↔q|4αo↓|4αo↓|4αo↓|4.|;{A9}|πThe measure 
 5603  of |εB|¬S(r,|4|≤e) |πis at most |ε|¬K|βk|β|¬R|βr|4ke|gα_↓|g|
 5608  ≤e|i2|gk, |πand this is the remainder of a convergent 
 5617  series so|'{A9}|uwlim|uc|)|.|εr|¬M|¬X|)|4(|πmeasure 
 5620  of |εB|¬S(r, |≤e){H12}){H10}|4α=↓|40.|J!(34)|;
 5623  {A9}!|9|7|πNow if |εx |πis a real number whose 
 5631  binary expansion |ε0.X|β0X|β1|4.|4.|4. |πleads 
 5635  to an in_nite sequence |ε|↔bX|βs|mn|↔v|λR |πthat 
 5641  is not 1-distributed, and if |ε|≤n(r) |πdenotes 
 5648  the number of zeros in the _rst |εr |πelements 
 5657  of the latter sequence, then|'{A9}|ε|¬G|≤n(r)/r|4α_↓|4|f1|d3
 5662  2|)|↔G|4|¬R|42|≤e,|;{A9}|πfor some |ε|≤e|4|¬Q|40 
 5666  |πand in_nitely many |εr. |πThis means |εx |πis 
 5674  in |εB|¬S(r,|4|≤e) |πfor all |εr. |πSo _nally 
 5681  we _nd that|'{A3}|εN(|λR, |λS)|4α=↓|4|uw|↔e|uc|)t|¬R2|)|4|uw
 5685  |↔E|)r|¬R1|)|4B|¬S(r, 1/t),|;{A9}|πand, by (34), 
 5690  |↔E|β|εr|β|¬R|β1|4B|¬S(r,|41/t) |πhas measure 
 5693  zero for all |εt. |πHence |εN(|λR,|4|λS) |πhas 
 5700  measure zero.|'{A12}!|9|7From the existence of 
 5706  |εbinary |πsequences satisfying De_nition R6, 
 5711  we can show the existence if [0,|41) sequences 
 5719  which are random in this sense. For details, 
 5727  see exercise 36. The consistency of De_nition 
 5734  R6 is thereby established.|'{A12}|≡E|≡.|9|≡R|≡a|≡n|≡d|≡o|≡m 
 5739  |≡_|≡n|≡i|≡t|≡e |≡s|≡e|≡q|≡u|≡e|≡n|≡c|≡e|≡s|≡.|9|4An 
 5741  argument was given above to indicate that it 
 5749  is impossible to de_ne the concept of randomness 
 5757  for _nite sequences; any given _nite sequence 
 5764  is as likely as any other. Still, nearly everyone 
 5773  would agree that the sequence 011101001 is ``more 
 5781  random'' than 101010101, and even the latter 
 5788  sequence is ``more random'' than 000000000. Although 
 5795  it is true that truly random sequences will exhibit 
 5804  locally nonrandom behavior, we would expect such 
 5811  behavior only in a long _nite sequence, not in 
 5820  a short one.|'!|9|7Several ways for de_ning the 
 5828  randomness of a _nite sequence have been proposed, 
 5836  and only a few of the ideas will be sketched 
 5846  here. Let us consider only the case of |εb|π-ary 
 5855  sequences.|'!|9|7Given a |εb-|πary sequence |εX|β1,|4X|β2,|4
 5860  .|4.|4.|4X|βN, |πwe can say that|'{A9}Pr{H12}({H10}|εS(n){H1
 5865  2}){H10}|4|¬V|4p,!!|πif!!|ε|¬G|≤n(N)/N|4α_↓|4p|¬G|4|¬E|41/|¬
 5865  H|v4N|),|;{A9}|πwhere |ε|≤n(n) |πis the quantity 
 5871  appearing in De_nition A at the beginning of 
 5879  this section. The above sequence can be called 
 5887  ``|εk-|πdistributed'' if|'{A9}Pr(|εX|βnX|βn|βα+↓|β1|4.|4.|4.
 5889  |4X|βn|βα+↓|βk|βα_↓|β1|4α=↓|4x|β1x|β2|4.|4.|4.|4x|βk)|4|¬V|4
 5889  1/b|gk|;{A9}|πfor all |εb-|πary numbers |εx|β1x|β2|4.|4.|4.|
 5894  4x|βk. (|πCf. De_nition D; unfortunately a sequence 
 5901  may be |εk-|πdistributed by this new de_nition 
 5908  when it is not (|εk|4α_↓|41)-|πdistributed.)|'
folio 214 galley 8
 5913  |Hu*?*?*?*?{U0}{H10L12M29}|πW58320#Computer Programming!(Knuth/A
 5914  ddison-Wesley)!f.|4214!ch.|43!g.|48d|'{A6}!|9|7A 
 5916  de_nition of randomness may now be given analogous 
 5924  to De_nition R1, as follows:|'{A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡i|≡o|
 5929  ≡n |≡Q|≡1|≡.|9|4|εA b-ary sequence of length 
 5935  N is ``random'' if it is k-distributed (in the 
 5944  above sense) for all positive integers k|4|¬E|4|πlog|ε|βb|4N
 5950  .|'{A12}!|9|7|πAccording to this de_nition, for 
 5956  example, there are 170 nonrandom binary sequences 
 5963  of length 11:|'{A9}|∂00000001111!!10000000111!!11000000011!!
 5966  11100000001|;00000001110!!10000000110!!11000000010!!11100000
 5967  000|;00000001101!!10000000101!!11000000001!!10100000001|;
 5969  00000001011!!10000000011!!01000000011!!01100000001|;
 5970  |L00000000111>{A9}plus 01010101010 and all sequences 
 5976  with nine or more zeros, plus all sequences obtained 
 5985  from the preceding ones by interchanging ones 
 5992  and zeros.|'!|9|7Similarly, we can formulate 
 5998  a de_nition for _nite sequences analogous to 
 6005  De_nition R6. Let |≡A be a set of algorithms, 
 6014  each of which is a combination selection and 
 6022  choice procedure that gives a subsequence |ε|↔bX|βs|mn|↔v|λR
 6028  , |πas in the proof of Theorem M.|'{A12}|≡D|≡e|≡_|≡n|≡i|≡t|≡
 6036  i|≡o|≡n |≡Q|≡2|≡.|9|4|εThe b-ary sequence X|β1,|4X|β2,|4.|4.
 6040  |4.|4,|4X|βN is (n,|4|≤e)-random with respect 
 6045  to a set of algorithms |π|≡A, |εif for every 
 6054  subsequence X|βt|m1,|4X|βt|m2,|4.|4.|4,|4X|βt|mm 
 6056  determined by an algorithm of |π|≡A |εwe have 
 6064  either m|4|¬W|4n or|'{A9}|↔g|4|(1|d2m|)|4|≤v|βa(X|βt|m1,|4.|
 6067  4.|4.|4,|4X|βt|mm)|4α_↓|4|(1|d2b|)|4|↔g|4|¬E|4|≤e!!|πfor!!|ε
 6067  0|4|¬E|4a|4|¬W|4b.|;{A9}|πHere |ε|≤n|βa(x|β1,|4.|4.|4.|4,|4x
 6069  |βm) |πis the number of |εa|π's in the sequence 
 6078  |εx|β1,|4.|4.|4.|4,|4x|βm.|'!|9|7|π(In other 
 6081  words, ev ery su∃ciently long subsequence determined 
 6088  by an algorithm of |≡A must be approximately 
 6096  equi|-distributed.) The basic idea in this case 
 6103  is to let |≡A be a set of ``simple'' algorithms; 
 6113  the number (and the complexity) of the algorithms 
 6121  in |≡A can grow as |εN |πgrows.|'!|9|7As an example 
 6131  of De_nition Q2, let us consider binary sequences, 
 6139  and let |≡A be just the following four algorithms:|'
 6148  {A12}!|9|7a)|9|1Take the whole sequence.|'!|9|7b)|9Take 
 6153  alternative terms of the sequence, starting with 
 6160  the _rst.|'!|9|7c)|9|1|1Take the terms of the 
 6167  sequence following a zero.|'!|9|7d)|9Take the 
 6173  terms of the sequence following a one.|'{A12}Now 
 6181  a sequence |εX|β1,|4.|4.|4.|4,|4X|β8 |πis (4,|4|f1|d38|))-ra
 6185  ndom if:|'{A12}{I2.11H}by|7(a),|9|1|¬G|f1|d38|)(|εX|β1|4α+↓|
 6187  4αo↓|4αo↓|4αo↓|4α+↓|4X|β8)|4α_↓|4|f1|d32|)|¬G|4|¬E|4|f1|d38|
 6187  ), |πif there are 3, 4, or 5 ones;|'{A6}by|7(b),|9|¬G|f1|d34
 6196  |)(|εX|β1|4α+↓|4X|β3|4α+↓|4X|β5|4α+↓|4X|β7)|4α_↓|4|f1|d32|)|
 6196  ¬G|4|¬E|4|f1|d38|), |πi.e., if there are two 
 6202  ones in odd-numbered positions.|'{A6}by|7(c),|9|1|1there 
 6207  are three possibilities depending on how many 
 6214  zeros occupy positions |εX|β1,|4.|4.|4.|4,|4X|β7: 
 6218  |πif there are 2 or 3 zeros here, there is no 
 6229  condition to test (since |εn|4α=↓|44); |πif there 
 6236  are 4 zeros, they must be followed by two zeros 
 6246  and two ones; and if there are 5 zeros, they 
 6256  must be followed by two or three zeros.|'{A12}{IC}by|7(d),|9
 6264  we get conditions similar to those implied by 
 6272  (c).|'!|9|7It turns out that only the following 
 6280  binary sequences of length 8 are (4,|4|f1|d38|))-random 
 6287  with respect to these rules:|'{A9}00001011!!00101001!!010011
 6292  10!!01101000|;00011010!!00101100!!01011011!!01101100|;
 6294  00011011!!00110010!!01011110!!01101101|;00100011!!00110011!!
 6295  01100010!!01110010|;00100110!!00110110!!01100011!!01110110|;
 6297  00100111!!00111001!!01100110!!!!!!|4|4|;{A9}plus 
 6299  those obtained by interchanging 0 and 1 consistently.|'
 6307  !|9|7It is clear that we could make the set of 
 6317  algorithms so large that no sequencex satisfy 
 6324  the de_nition, when |εn |πand |ε|≤e |πare reasonably 
 6332  small. A. N. Kolomogorov has proved that an (|εn,|4|≤e)-|πra
 6340  ndom binary sequence |εwill |πalways exist, for 
 6347  any given |εN, |πif the number of algorithms 
 6355  in |≡A |πdoes not exceed|'{A9}|ε|f1|d32|)e|g2|gn|g|≤e|i2|g(|
 6360  g1|gα_↓|g|≤e|g).|J!(35)|;{A9}|πThis result is 
 6364  not nearly strong enough to show that sequences 
 6372  satisfying De_nition Q1 will exist, but the latter 
 6380  can be constructed e∃ciently using the procedure 
 6387  of Rees in exercise 3.2.2-21.|'!|9|7Still another 
 6394  interesting approach to a de_nition of randomness 
 6401  has been taken by Per Martin-L|=4of [|εInformation 
 6408  and Control |≡9 (1966), |π602<619]. Given a _nite 
 6416  |εb-|πary sequence |εX|β1,|4.|4.|4.|4,|4X|βN, 
 6419  |πlet |ε|λ3(X|β1,|4.|4.|4.|4,|4X|βN) |πbe the 
 6423  length of the shortest Turing machine program 
 6430  which generates this sequence. (For a de_nition 
 6437  of Turing machines, see Chapter 11; alternatively, 
 6444  we could use certain |πclasses of e=ective algorithms, 
 6452  such as those de_ned in exercise 1.1<8.) Then 
 6460  |λ3(|εX|β1,|4.|4.|4.|4,|4X|βN) |πis a measure 
 6464  of the ``patternlessness'' of the sequence, and 
 6471  we may equate this idea with randomness. The 
 6479  sequences of length |εN |πwhich maximize |ε|λ3(X|β1,|4.|4.|4
 6485  .|4,|4X|βN) |πmay be called random. (From the 
 6492  standpoint of practical random-number generation 
 6497  by computer, this is, of course, the worst de_nition 
 6506  of ``randomness'' that can be imagined*3)|'!|9|7Essentially 
 6513  the same de_nition of randomness was independently 
 6520  given by G. Chaitin at about the same time; see 
 6530  |εJ|4ACM|4|≡1|≡6 (1969), 145<159. |πIt is interesting 
 6536  to note that eaen though this de_nition makes 
 6544  no reference to equi|-distribution properties 
 6549  as our other de_nitions have, Martin-L|=4of and 
 6556  Chaitin have proved that random sequences of 
 6563  this type also have the expected equi|-distribution 
 6570  properties. In fact, Martin-L|=4of has demonstrated 
 6576  that such sequences satisfy |εall |πcomputable 
 6582  statistical tests for randomness, in an appropriate 
 6589  sense.|'{A12}|≡F|≡.|9|≡S|≡u|≡m|≡m|≡a|≡r|≡y|≡, 
 6591  |≡h|≡i|≡s|≡t|≡o|≡r|≡y|≡, |≡a|≡n|≡d |≡b|≡i|≡b|≡l|≡i|≡o|≡g|≡r|
 6593  ≡a|≡p|≡h|≡y|≡.|9|4We have de_ned several degrees 
 6598  of randomness that a sequence might possess.|'
 6605  !|9|7!|9|7An in_nite sequence which is |¬X-distributed 
 6611  satis_es a great many useful properties which 
 6618  are expected of random sequences, and there is 
 6626  a rich theory concerning |¬X-distributed sequences. 
 6632  (The exercises which follow develop several important 
 6639  properties of |¬X-distriguted sequences which 
 6644  have not been mentioned in the text.) De_nition 
 6652  R1 is therefore an appropriate basis for theoretical 
 6660  studies of randomness.|'!|9|7The concept of an 
 6667  |¬X-distributed |εb-|πary sequence was introduced 
 6672  in 1909 by Emile Borel. He essentially de_ned 
 6680  the concept of an (|εm,|4k)-|πdistributed sequence, 
 6686  and showed that the |εb-|πary representations 
 6692  of almost all real numbers are (|εm,|4k)-|πdistributed 
 6699  for all |εm |πand |εk. |πHe called such numbers 
 6708  |εnormal |πto base |εb. |πAn excellent discussion 
 6715  of this topic appears in his well-known book, 
 6723  |εLe|=&cons sur la th|=1eorie des fonctions (|π2nd 
 6730  ed., 1914), 182<216.|'!|9|7The notion of an |¬X-distributed 
 6738  sequence of |εreal |πnumbers, also called a |εcompletely 
 6746  equidistributed sequence, |πwas introduced by 
 6751  N. M. Korobov in |εDoklady Akad. Nauk |πSSSR 
 6759  |≡6|≡2 (1948), 21<22. He and several colleagues 
 6766  developed the theory of such sequences quite 
 6773  extensively during the 1950s in a series of papers. 
 6782  The book |εUniform Distribution of Sequences 
 6788  |πby L. Kuipers and H. Niederreiter (New York: 
 6796  Wiley, 1974) is an extraordinarily complete source 
 6803  of information about the rich mathematical literature 
 6810  concerning |εk-|πdistributed sequences of all 
 6815  kinds.|'!|9|7We have seen, however, that |¬X-distributed 
 6822  sequences need not be su∃ciently haphazard to 
 6829  qualify completely as ``random.'' Three de_nitions, 
 6835  R4, R5, and R6, were formulated above to provide 
 6844  the additional conditions; and De_nition R6, 
 6850  in particular, seems to be an appropriate way 
 6858  to de_ne the concept of an in_nite random sequence. 
 6867  It is a precise, quantitative statement that 
 6874  may well coincide with the intuitive idea of 
 6882  true randomness.|'|Ha*?*?*?*?{U0}{H10L12M29}|πW58320#Computer 
folio 216 galley 9
 6885  Programming!(Knuth/Addison-Wesley)!f.|4216!ch.|43!g.|49d|'
 6886  {A6}Historically, the development of these de_nitions 
 6892  was primarily in⊗uenced by R. von Mises' quest 
 6900  for a good de_nition of ``probability.'' In |εMath. 
 6908  Zeitschrift |≡5 |π(1919), 52<99, von Mises proposed 
 6915  a de_nition similar in spirit to De_nition R5, 
 6923  although stated too strongly (like our De_nition 
 6930  R3) so that no sequences satisfying the conditions 
 6938  could possibly exist. Many people noticed this 
 6945  discrepancy, and A. H. Copeland [|εAmer. J. Math. 
 6953  |≡5|≡0 (1928), 535<552] |πsuggested weakening 
 6958  von Mises' de_nition by substituting what he 
 6965  called ``admissible numbers'' (or Bernoulli sequences). 
 6971  These are equivalent to |¬X-distributed [0,|41) 
 6977  sequences in which all entries |εU|βn |πhave 
 6984  been replaced by 1 if |εU|βn|4|¬W|4p |πor by 
 6992  0 if |εU|βn|4|¬R|4p, |πfor a given probability 
 6999  |εp. |πThus Copeland was essentially suggesting 
 7005  a return to De_nition R1. Then Abraham Wald showed 
 7014  that it is not necessary to weaken von Mises' 
 7023  de_nition so drastically, and he proposed substituting 
 7030  a countable set of subsequence rules. In an important 
 7039  paper [|εErgebnisse eines math. Kolloquiums |≡8 
 7045  (|πVienna, 1937), 38<72], Wald essentially proved 
 7051  Theorem W, although he made the erroneous assertion 
 7059  that the sequence constructed by Algorithm W 
 7066  also satis_es the stronger condition that Pr(|εU|βn|4|¬A|4A)
 7072  |4α=↓|4|πmeasure of |εA, |πfor all Lebesgue Measurable 
 7079  |εA|4|↔Y|4[0,|41). |πWe have observed that no 
 7085  sequence can satisfy this property.|'!|9|7The 
 7091  concept of ``computability'' was still very much 
 7098  in its infancy when Wald wrote his paper, and 
 7107  A. Church [|εBulletin AMS |≡4|≡7 (1940), |π130<135] 
 7114  showed how the precise notion of ``e=ective algorithm'' 
 7122  could be added to Wald's theory to make his de_nitions 
 7132  completely rigorous. The extension to De_nition 
 7138  R6 was due essentially to A. N. Kolmogorov [|εSankhy|=|¬3a 
 7147  |πseries A, |≡2|≡5 (1963), 369<376], who proposed 
 7154  De_nition Q2 for _nite sequences in that same 
 7162  paper.|'!|9|7Another important contribution was 
 7167  made by Donald W. Loveland [|εZeitschr. f. math. 
 7175  Logik und Grundlagen d. Math. |≡1|≡2 (1966), 
 7182  279<294], |πwho discussed De_nitions R4, R5, 
 7188  R6, and several concepts in between. Loveland 
 7195  proved that there are R5|4α=↓|4random sequences 
 7201  which do not satisfy R4, thereby establishing 
 7208  the need for a stronger de_nition such as R6. 
 7217  In fact, he de_ned a rather simple permutation 
 7225  |↔b|εf(n)|↔v |πof the nonnegative integers, and 
 7231  an Algorithm W|¬S analogous to Algorithm W, such 
 7239  that |v4Pr|)(|εU|βf|β(|βn|β)|4|¬R|4|f1|d32|))|4α_↓|4|πPr(|εU
 7240  |βf|β(|βn|β)|4|¬R|4|f1|d32|))|4|¬R|4|f1|d32|) 
 7241  |πfor every R5|4α=↓|4random sequence |ε|↔bU|βn|↔v 
 7246  |πproduced by Algorithm W|¬S when it is given 
 7254  an in_nite set of subsequence rules |λR|ε|βk. 
 7261  |πSchnorr's subsequent book |εZuf|=4alligkeit 
 7265  und Wahrscheinlichkeit [Lecture Notes in Math. 
 7271  |≡2|≡1|≡8 (|πBerlin: Springer, 1971)] gives a 
 7277  much more detailed treatment of the entire subject 
 7285  of randomness than could be provided here and 
 7293  makes an excellent introduction to the ever-growing 
 7300  advanced literature on the topic.|'!|9|7The publications 
 7307  of Church and Kolmogorov considered only binary 
 7314  sequences for which Pr(|εX|βn|4α=↓|41)|4α=↓|4p 
 7318  |πfor a given probability |εp. |πThe discussion 
 7325  which appears in this section is slightly more 
 7333  general, since a [0,|41) sequence essentially 
 7339  represents all |εp |πat once.|'!|9|7In another 
 7346  paper [|εProblemy Pereda|=|≠3ci Inform acci |≡1 
 7352  (1965), 3<11], |πKolmogorov considered the problem 
 7358  of de_ning the ``information content'' of a sequence, 
 7366  and this work led to Chaitin and Martin-L|=4of's 
 7374  interesting de_nition of _nite random sequences 
 7380  via ``patternlessness.'' (See |εIEEE Trans. |π|≡I|≡T|≡-|≡1|≡
 7385  4 (1968), 662<664.) Another de_nition of randomness, 
 7392  somewhere ``between'' De_nitions Q1 and Q2, had 
 7399  been formulated many years earlier by A. S. Besicovitch 
 7408  [|εMath. Zeitschrift |≡3|≡9 (|π1934), 146<156].|'
 7413  !|9|7For further discussion of random sequences, 
 7419  see K. R. Popper, |εThe Logic of Scienti⊂c Discovery 
 7428  (|πLondon, 1959), especially the interesting 
 7433  construction on pp. 162<163, which he _rst published 
 7441  in 1934.|'{A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A12}{H9L11}|9|1
 7444  |≡1|≡.|9|4[|*/|↔O|↔c|\] Can a periodic sequence 
 7449  be equidistributed?|'{A3}|9|1|≡2|≡.|9|4[|*/|↔O|↔c|\] 
 7452  Consider the periodic binary sequence 0,|40,|41,|41,|40,|40,
 7457  |41,|41,|4.|4.|4.|4. Is it 1-distributed? Is 
 7462  it 2-distributed? Is it 3-distributed?|'{A3}|9|1|≡3|≡.|9|4[|
 7467  ε|*/M|↔P|↔P|\] |πConstruct a periodic ternary 
 7472  sequence which is 3-distributed.|'{A3}|9|1|≡4|≡.|9|4[|ε|*/HM|
 7476  ↔P|↔P|\] |πLet |εU|βn|4α=↓|4(2|g|"l|g|πl|gg|g(|ε|gn|gα+↓|g1|
 7478  g)|g|"L/3)|πmod|41. What is Pr(|εU|βn|4|¬W|4|f1|d32|))?|'
 7482  {A3}|9|1|≡5|≡.|9|4[|*/HM|↔O|↔M|\] |πProve that 
 7485  Pr{H11}({H9}|εS(n) |πand T(n){H11}){H9}|4α+↓|4Pr{H11}({H9}|ε
 7487  S(n) |πor |εT(n){H11}){H9}|4α=↓|4|πPr{H11}({H9}|εS(n){H11}){
 7489  H9}|4α+↓|4|πPr{H11}({H9}|εT(n){H11}){H9}, |πfor 
 7491  any two statements |εS(n), T(n), |πprovided at 
 7498  least three of the limits exist. [For example, 
 7506  if a sequence is 2-distributed, we would _nd 
 7514  that|'{A9}{H9}Pr(|εu|β1|4|¬E|4U|βn|4|¬W|4v|β1!!|πor!!|εu|β2|
 7515  4|∂|¬E|4U|βn|βα+↓|β1|4|¬W|4v|β2)|hα_↓(v|β1|4α_↓|4u|β1))v|β2|
 7515  4α_↓|4u|β2).]|n|;{A4}|Lα=↓|4v|β1|4α_↓|4u|β1|4α+↓|4v|β2|4α_↓|
 7516  4u|β2|4α_↓|4(v|β1|4α_↓|4u|β1)(v|β2|4α_↓|4u|β2).]>
 7517  {A9}|9|1|≡6|≡.|9|4[|*/HM|↔P|↔L|\] |πLet |εS|β1(n), 
 7520  S|β2(n),|4.|4.|4. |πbe an in_nite sequence of 
 7526  statements about mutually disjoint events, i.e., 
 7532  |εS|βi(n) |πand |εS|βj(n) |πcannot simultaneously 
 7537  be true if |εi|4|=|↔6α=↓|4j. |πAssume that Pr{H11}({H9}S|βj(
 7543  n){H11}){H9} exists for each |εj|4|¬R|41. |πShow 
 7549  that Pr{H11}({H9}|εS|βj(n) |πis true for some 
 7555  |εj|4|¬R|41{H11}){H9}|4|¬R|4|¬K|βj|β|¬R|β1|4|πPr{H11}({H9}|ε
 7555  S|βj(n){H11}){H9}, |πand give an example to show 
 7562  that equality need not hold.|'{A3}|9|1|≡7|≡.|9|4[|ε|*/HM|↔P|↔
 7567  p|\] |πAs in the previous exercise, let |εS|βi|βj(n), 
 7575  i|4|¬R|41, j|4|¬R|41, |πbe in_nitely many mutually 
 7581  disjoint events, such that Pr{H11}({H9}|εS|βi|βj(n){H11}){H9
 7585  } |πexists. Assume that for all |εn|4|¬Q|40, 
 7592  S|βi|βj(n) |πis true for exactly one pair of 
 7600  integers |εi,|4j. |πIf |¬K|ε|βi|β,|βj|β|¬R|β1|4|πPr{H11}({H9
 7603  }|εS|βi|βj(n){H11}){H9}|4α=↓|41, |πcan it be 
 7607  concluded that, for all |εi|4|¬R|41, |πPr{H11}({H9}|εS|βi|βj
 7612  (n) |πis true for some |εj|4|¬R|41{H11}){H9} 
 7618  |πexists and equals |¬K|ε|βj|β|¬R|β1|4|πPr{H11}({H9}|εS|βi|β
 7621  j(n){H11}){H9}?|'{A3}|9|1|≡8|≡.|9|4[M|*/|↔O|↔C|\] 
 7623  |πProve (13).|'{A3}|9|1|≡9|≡.|9|4[|εHM|*/|↔P|↔c|\] 
 7626  |πProve Lemma E. [|εHint|*/: |\|πConsider |¬K|ε|β1|β|¬E|βj|β|
 7631  ¬E|βm|4(y|βj|βn|4α_↓|4|≤a)|g2.]|'{A3}|≡1|≡0|≡.|9|4[|*/HM|↔P|↔
 7632  P|\] |πWhere was the fact that |εq |πis a multiple 
 7642  of |εm |πused in the proof of Theorem C?|'{A3}|≡1|≡1|≡.|9|4|
 7651  ε[M|*/|↔O|↔c|\] |πUse Theorem C to prove that 
 7658  if |↔b|εU|βn|↔v |πis |¬X-distributed, so is the 
 7665  subsequence |ε|↔bU|β2|βn|↔v.|'{A3}|≡1|≡2|≡.|9|4[|*/HM|↔P|↔c|\
 7667  ] |πShow that a |εk-|πdistributed sequence passes 
 7674  the ``maximum of |εk'' |πtest, in the following 
 7682  sense: Pr{H11}({H9}|εu|4|¬E|4|πmax(|εU|βn,|4U|βn|βα+↓|β1,|4.
 7683  |4.|4.|4,|4U|βn|βα+↓|βk|βα_↓|β1)|4|¬W|4v{H11}){H9}|4α=↓|4v|g
 7683  k|4α_↓|4u|gk.|'{A3}|≡1|≡3|≡.|9|4[|*/HM|↔P|↔p|\] 
 7685  |πShow that an |¬X-distributed [0,|41) sequence 
 7691  passes the ``gap test'' in the following sense: 
 7699  If If 0|4|¬E|4|ε|≤a|4|¬W|4|≤b|4|¬E|41, |πand 
 7703  |εp|4α=↓|4|≤b|4α_↓|4|≤a, |πlet |εf(0)|4α=↓|40, 
 7706  |πand for |εn|4|¬R|41, |πlet |εf(n) |πbe the 
 7713  smallest integer |εm|4|¬Q|4f(n|4α_↓|41) |πsuch 
 7717  that |ε|≤a|4|¬E|4U|βm|4|¬W|4|≤b; |πthen Pr{H11}({H9}|εf(n)|4
 7720  α_↓|4f(n|4α_↓|41)|4α=↓|4k{H11}){H9}|4α=↓|4p(1|4α_↓|4p)|gk|gα
 7720  _↓|g1.|'{A3}|≡1|≡4|≡.|9|4[|*/HM|↔P|↔C|\] |πShow 
 7723  that an |¬X-distributed sequence passes the ``run 
 7730  test'' in the following sense: If |εf(0)|4α=↓|41 
 7737  |πand if for |εn|4|¬R|41 f(n) |πis the smallest 
 7745  integer |εm|4|¬Q|4f(n|4α_↓|41) |πsuch that |εU|βm|βα_↓|β1|4|
 7749  ¬Q|4U|βm, |πthen|'{A9}Pr{H11}({H9}|εf(n)|4α_↓|4f(n|4α_↓|41)|
 7751  4α=↓|4{H11}){H9}|4α=↓|42k/(k|4α+↓|41)*3|4α_↓|42(k|4α+↓|41)/(k
 7751  |4α+↓|42)*3.|;{A9}|≡1|≡5|≡.|9|4[|*/HM|↔L|↔c|\] 
 7753  |πShow that an |¬X-distributed sequence passes 
 7759  the ``coupon-collector's test'' when there are 
 7765  only two kinds of coupons, in the following sense` 
 7774  Let |εX|β1,|4X|β2,|4.|4.|4. |πbe an |¬X-distributed 
 7779  binary sequence. Let |εf(0)|4α=↓|40, |πand for 
 7785  |εn|4|¬R|41 |πlet |εf(n) |πbe the smallest integer 
 7792  |εm|4|¬Q|4f(n|4α_↓|41) |πsuch that |¬T|εX|βf|β(|βn|βα_↓|β1|β
 7795  )|βα+↓|β1,|4.|4.|4.|4,|4X|βm|¬Y |πis the set 
 7799  |¬T0,|41|¬Y. Prove that Pr{H11}({H9}|εf(n)|4α_↓|4f(n|4α_↓|41
 7802  )|4α=↓|4k{H11}){H9}|4α=↓|42|g1|gα_↓|gk, k|4|¬R|42. 
 7804  |π(Cf. exercise 7.)|'|≡1|≡6|≡.|9|4[|ε|*/HM|↔L|↔l|\] 
 7808  |πDoes the coupon-collector's test hold for |¬X-distributed 
 7815  sequences when there are more than two kinds 
 7823  of coupons? (Cf. the previous exercise.)|'{A3}|≡1|≡7|≡.|9|4|
 7829  ε[|*/HM|↔C|↔c|\] |πGiven that |εr |πis a rational 
 7836  number, Franklin has proved that the sequence 
 7843  with |εU|βn|4α=↓|4(r|gn|4|πmod|41) is not 2-distributed. 
 7848  But is there any rational number |εr |πfor which 
 7857  this sequence is equidistributed? In particular, 
 7863  is the sequence equidistributed when |εr|4α=↓|4|f3|d32|)? 
 7869  (|πCf. the article by K. Mahler, |εMathematika 
 7876  |≡4 (|π1957), 122<124.)|'{A3}|≡1|≡8|≡.|9|4[|ε|*/HM|↔P|↔P|\] 
 7880  |πProve that if |εU|β0,|4U|β1,|4.|4.|4. |πis 
 7885  |εk-|πdistributed, so is the sequence |εV|β0,|4V|β1,|4.|4.|4
 7890  .|4, |πwhere |εV|βn|4α=↓|4|"lnU|βn|"L/n.|'{A3}|≡1|≡9|≡.|9|4[
 7893  |ε|*/HM|↔L|↔C|\] |πConsider De_nition R4 with 
 7898  ``|¬X-distributed'' replaced by ``1-distributed''. 
 7902  Is there a sequence which satis_es this weaker 
 7910  de_nition, but which is not |¬X-distributed? 
 7916  (Is the weaker de_nition really weaker?)|'{A3}|≡2|≡0|≡.|9|4[
 7922  |ε|*/HM|↔M|↔o|\] |πDoes the sequence with |εU|βn|4{U0}{H10L12
folio 220 galley 10
 7927  M29}|πW58320#Computer Programming!(Knuth/Addison-Wesley)!f.|
 7928  4220!ch.|43!g.|410d|'{A6}|≡2|≡1|≡.|9|4|ε[|*/HM|↔P|↔c|\] 
 7930  |πLet |εS |πbe a set and let |λM be a collection 
 7941  of subsets of |εS. |πSuppose that |εp |πis a 
 7950  real-valued function of the sets in |λM, for 
 7958  which |εp(M) |πdenotes the probability that a 
 7965  ``randomly'' chosen element of |εS |πlies in 
 7972  |εM. |πGeneralize De_nitions B and D to obtain 
 7980  a good de_nition of the concept of a |εk-|πdistributed 
 7989  sequence |ε|↔bZ|βn|↔v |πof elements of |εS |πwith 
 7996  respect to the probability distribution |εp.|'
 8002  {A3}|≡2|≡2|≡.|9|4[|*/HM|↔L|↔c|\] (|πHermann Weyl.) 
 8005  Show that the [0,|41) sequence |ε|↔bU|βn|↔v |πis 
 8012  |εk-|πdistributed if and only if|'{A4}|uwlim|uc|)|.|εN|¬M|¬X
 8017  |)|4|(1|d2N|)|4|↔k|uc|)0|¬En|¬WN|)|4|πexp{H11}({H9}|ε2|≤pi(c
 8017  |β1U|βn|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|βkU|βn|βα+↓|βk|βα_↓|β1){
 8017  H11}){H9}|4α=↓|40|;{A6}{A3}|πfor every set of 
 8022  integers |εc|β1,|4c|β2,|4.|4.|4.|4,|4c|βk |πnot 
 8025  all zero.|'{A3}|≡2|≡3|≡.|9|4[|ε|*/M|↔L|↔M|\] |πShow 
 8029  that a |εb-|πary sequence |ε|↔bX|βn|↔v |πis |εk-|πdistribute
 8035  d if and only if all of the sequences |ε|↔bc|β1X|βn|4α+↓|4c|
 8044  β2X|βn|βα+↓|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|βkX|βn|βα+↓|βk|βα
 8044  _↓|β1|↔v |πare |εequidistributed, |πwhenever 
 8048  |εc|β1,|4c|β2,|4.|4.|4.|4,|4c|βk |πare integers 
 8051  with gcd (|εc|β1,|4.|4.|4.|4,|4c|βk)|4α=↓|41.|'
 8054  {A3}{H9}|≡2|≡4|≡.|9|4[|*/M|↔L|↔c|\] |πShow that 
 8057  a [0,|41) sequence |ε|↔bU|βn|↔v |πis |εk-|πdistributed 
 8063  if and only if all of the sequences |ε|↔bc|β1U|βn|4α+↓|4c|β2
 8071  U|βn|βα+↓|β1|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4c|βkU|βn|βα+↓|βk|βα_↓
 8071  |β1|↔v |πare |εequidistributed, |πwhenever |εc|β1,|4c|β2,|4.
 8075  |4.|4.|4,|4c|βk |πare integers not all zero.|'
 8081  {A3}|≡2|≡5|≡.|9|4[|ε|*/HM|↔P|↔c|\] |πA sequence 
 8084  is called a ``white sequence'' if all serial 
 8092  correlations are zero, i.e., if the equation 
 8099  in Corollary S is true for |εall k|4|¬R|41. (|πBy 
 8108  Corollary S, an |¬X-distributed sequence is white.) 
 8115  Show that if a [0,|41) sequence is equidistributed, 
 8123  it is white if and only if|'{A9}|uwlim|uc|)|.|εn|¬M|¬X|)|4|(
 8130  1|d2n|)|4|↔k|uc|)0|¬Ej|¬Wn|)|4(U|βj|4α_↓|4|f1|d32|))(U|βj|βα
 8130  +↓|βk|4α_↓|4|f1|d32|))|4α=↓|40,!!|πall!!|εk|4|¬R|41.|;
 8131  {A9}|≡2|≡6|≡.|9|4[|*/HM|↔L|↔M|\] (|πJ. Franklin.) 
 8134  A white sequence, as de_ned in the previous exercise, 
 8143  can de_nitely fail to be random. Let |εU|β0,|4U|β1,|4.|4.|4.
 8150   |πbe an |¬X-distributed sequence; de_ne the 
 8157  sequence |εV|β0,|4V|β1,|4.|4.|4. |πas follows:|'
 8161  {A9}|ε(V|β2|βn|βα_↓|β1,|4V|β2|βn)|4α=↓|4(U|β2|βn|βα_↓|β1,|4U
 8161  |β2|βn)!!|πif!!(|εU|β2|βn|βα_↓|β1,|4U|β2|βn)|4|¬A|4G,|;
 8162  {A4}(V|β2|βn|βα_↓|β1,|4V|β2|βn)|4α=↓|4(U|β2|βn,|4U|β2|βn|βα_
 8162  ↓|β1)!!|πif!!|ε(U|β2|βn|βα_↓|β1,|4U|β2|βn)|4|=|↔6|¬A|4G,|;
 8163  {A9}|πwhere |εG |πis the set |¬T(|εx,|4y)|4|¬G|4x|4α_↓|4|f1|
 8168  d32|)|4|¬E|4y|4|¬E|4x |πor |εx|4α+↓|4|f1|d32|)|4|¬E|4y|¬Y. 
 8171  |πShow that (a) |εV|β0,|4V|β1,|4.|4.|4. |πis 
 8176  equidistributed and white; (b) Pr(|εV|βn|4|¬Q|4V|βn|βα+↓|β1)
 8180  |4α=↓|4|f5|d38|). (|πThis points out the weakness 
 8186  of the serial correlation test.)|'{A3}|ε|≡2|≡7|≡.|9|4[|*/HM|↔
 8191  M|↔m|\] |πWhat is the highest possible value 
 8198  for Pr(|εV|βn|4|¬Q|4V|βn|βα+↓|β1- |πin an equidistributed, 
 8203  white sequence? (D. Coppersmith [to appear] has 
 8210  constructed such a sequence achieving the value 
 8217  |f7|d38|).)|'{A3}|ε|≡2|≡8|≡.|9|4[HM|*/|↔P|↔O|\] 
 8219  |πUse the sequence (11) to construct a [0,|41) 
 8227  sequence which is 3-distributed, for which Pr(|εU|β2|βn|4|¬R
 8233  |4|f1|d32|))|4α=↓|4|f3|d34|).|'{A3}|≡2|≡9|≡.|9|4[HM|*/|↔L|↔M|
 8234  \] |πLet |εX|β0,|4X|β1,|4.|4.|4. |πbe a (|ε2k)-|πdistributed
 8239   binary sequence. Show that|'{A9}|v4Pr|)(|εX|β2|βn|4α=↓|40)|
 8244  4|¬E|4|f1|d32|)|4α+↓|4|↔a|(2k|4α_↓|41|d5k|)|↔s|↔h2|g2|gk.|;
 8245  {A9}|≡3|≡0|≡.|9|4|ε[|*/M|↔L|↔m|\] |πConstruct 
 8247  a binary sequence which is (|ε2k)-|πdistributed, 
 8253  and for which|'{A9}Pr(|εX|β2|βn|4α=↓|40)|4α=↓|4|f1|d32|)|4α+
 8256  ↓|4|↔a|(2k|4α_↓|41|d5k|)|↔s|↔h2|g2|gk.|;{A9}(|πTherefore 
 8258  the inequality in the previous exercise is the 
 8266  best possible.)|'{A3}|ε|≡3|≡2|≡.|9|4[|*/M|↔P|↔M|\] 
 8269  |πGiven that |ε|↔bX|βn|↔v |πis a ``random'' |εb-|πary 
 8276  sequence according to De_nition R5, and if |ε|λR 
 8284  |πis a computable subsequence rule which speci_es 
 8291  an in_nite subsequence |ε|↔bX|βn|↔v|λR, |πshow 
 8296  that the latter subsequence is not only 1-distributed, 
 8304  it is ``random'' by De_nition R5.|'{A3}|ε|≡3|≡3|≡.|9|4[|*/HM|
 8310  ↔P|↔M|\] |πLet |ε|↔bU|βs|mn|↔v |πand |ε|↔bU|βs|mn|↔v 
 8315  |πbe in_nite disjoint subsequences of a sequence 
 8322  |ε|↔bU|βn|↔v. |π(Thus, |εr|β0|4|¬W|4r|β1|4|¬W|4r|β2|4|¬W|4αo
 8324  ↓|4αo↓|4αo↓ |πand |εs|β0|4|¬W|4s|β1|4|¬W|4s|β2|4|¬W|4αo↓|4αo
 8326  ↓|4αo↓ |πare increasing sequences of integers 
 8332  and |εr|βm|4|=|↔6α=↓|4s|βn |πfor any |εm,|4n.) 
 8337  |πLet |ε|↔bU|βt|mn|↔v |πbe the combined subsequence, 
 8343  so that |εt|β0|4|¬W|4t|β1|4|¬W|4t|β2|4|¬W|4αo↓|4αo↓|4αo↓ 
 8346  |πand the set |¬T|εt|βn|¬Y|4α=↓|4|¬Tr|βn|¬Y|4|↔q|4|¬Ts|βn|¬Y
 8349  . |πShow that if Pr(|εU|βr|mn|4|¬A|4A)|4α=↓|4|πPr(|εU|βs|mn|
 8353  4|¬A|4A)|4α=↓|4p, |πthen Pr(|εU|βt|mn|4|¬A|4A)|4α=↓|4p.|'
 8356  {A3}|≡3|≡4|≡.|9|4[|*/M|↔P|↔C|\] |πDe_ne subsequence 
 8359  rules |λR|β1,|4|λR|β2,|4|λR|β3,|4.|4.|4. such 
 8362  that Algorithm W can be used with these rules 
 8371  to give an e=ective algorithm to construct a 
 8379  [0,|41) sequence satisfying De_nition R1.|'{A3}|≡3|≡5|≡.|9|4
 8384  |ε[|*/HM|↔L|↔C|\] |π(D. W. Loveland.) Show that 
 8390  if a binary sequence |ε|↔bX|βn|↔v |πis R5|4α=↓|4random, 
 8397  and if |ε|↔bs|βn|↔v |πis any computable sequence 
 8404  as in De_nition R4, we must have |v4Pr|)(|εX|βs|mn|4α=↓|41)|
 8411  4|¬R|4|f1|d32|) |πand Pr(|εX|βs|mn|4α=↓|41)|4|¬E|4|f1|d32|).
 8413  |'{A3}|≡3|≡6|≡.|9|4[|*/HM|↔L|↔c|\] |πLet |ε|↔bX|βn|↔v 
 8417  |πbe a binary sequence which is ``random'' according 
 8425  to De_nition R6. Show that the [0,|41) sequence 
 8433  |ε|↔bU|βn|↔v |πde_ned in binary notation by the 
 8440  scheme|'{A9}|ε|∂U|β0|4α=↓|40.X|β0|hX|β7X|β9X|β9|n|;
 8442  {A4}|LU|β1|4α=↓|40.X|β1X|β2>{A4}|LU|β2|4α=↓|40.X|β3X|β4X|β5>
 8444  {A4}|LU|β3|4α=↓|40.X|β6X|β7X|β8X|β9>{A2}|Lαo↓|4αo↓|4αo↓>
 8446  {A9}|πis random in the sense of De_nition R6.|'
 8454  {A3}|ε|≡3|≡7|≡.|9|4[|*/M|↔M|↔c|\] (|πD. Coppersmith.) 
 8457  De_ne a sequence which satis_es De_nition R4 
 8464  but not De_nition R5. [|εHint|*/: |\|πConsider 
 8470  changing |εU|β0, U|β1, U|β4, U|β9,|4.|4.|4. |πin 
 8476  a truly random sequence.]|'|H*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 8480